{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib\n",
    "%matplotlib inline \n",
    "\n",
    "matplotlib.rc('figure', figsize=(12, 5))\n",
    "font = {'family' : 'normal',\n",
    "        'weight' : 'bold',\n",
    "        'size'   : 16}\n",
    "\n",
    "matplotlib.rc('font', **font)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simulated annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# September 2018 - Luke Harold Miles - Public Domain\n",
    "# Simulated annealing solution to traveling salesman problem\n",
    "# adapted from https://gist.github.com/qpwo/a46274751cc5db2ab1d936980072a134\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def find_tour(cities, dist_fun, iterations=10**5):\n",
    "    def calc_distance():\n",
    "        \"\"\"sum of distance to and from i and j in tour\n",
    "        \"\"\"\n",
    "        return sum(\n",
    "            dist_fun(\n",
    "                cities[tour[k % n]],\n",
    "                cities[tour[(k + 1) % n]]\n",
    "            )\n",
    "            for k in [j - 1, j, i - 1, i]\n",
    "        )\n",
    "    \n",
    "    n = len(cities)\n",
    "    # initial tour randomly initialized\n",
    "    tour = np.random.permutation(n)\n",
    "    lengths = []\n",
    "    for temperature in np.logspace(4, 0, num=iterations):\n",
    "        i = np.random.randint(n - 1) # city 1\n",
    "        j = np.random.randint(i + 1, n) # city 2\n",
    "        old_length = calc_distance()\n",
    "        tour[[i, j]] = tour[[j, i]] # swap i and j in tour\n",
    "        new_length = calc_distance()\n",
    "        if np.exp((old_length - new_length) / temperature) < np.random.random():  # swap was mistake\n",
    "            tour[[i, j]] = tour[[j, i]]  # swap them back\n",
    "            lengths.append(old_length)\n",
    "        else:\n",
    "            lengths.append(new_length)            \n",
    "    return tour, lengths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "def plot_solution(cities, tour):\n",
    "    xcoords, ycoords = list(zip(*cities[tour].tolist(), cities[tour[0]].tolist()))\n",
    "    plt.plot(xcoords, ycoords, 'xb-')\n",
    "    plt.show() # graph the tour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "cities = np.random.randint(0, 100, (15, 2))\n",
    "# scipy.spatial.distance.euclidean\n",
    "def euclidean_distance(c1, c2):\n",
    "    return np.linalg.norm(c1 - c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.spatial.distance import euclidean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length: 78.76978050285095\n"
     ]
    }
   ],
   "source": [
    "tour, lengths = find_tour(cities, euclidean, iterations=1000000)\n",
    "print(f'length: {lengths[-1]}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "findfont: Font family ['normal'] not found. Falling back to DejaVu Sans.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD4CAYAAAAJmJb0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO2dd3xUZfb/3w9dLKA0EVCajSIgoSMQTJSACkwAC8rqqnFdBRUQ3XWx4LqrqCgKrCIqIKIiVSxIMTQBJRQJ/asUF5BiYWnSwvP748z8JsQkJJly79w579drXjdzZzJz7pTPnHue83weY61FURRF8SbFnA5AURRFiRwq8oqiKB5GRV5RFMXDqMgriqJ4GBV5RVEUD1PC6QCyU7FiRVuzZk2nw1AURYkpVqxY8bO1tlJut7lK5GvWrElGRobTYSiKosQUxpjted2m5RpFURQPc0aRN8a8ZozZY4yxxphPs+2/0hizxBhzzBizyRhzXbbb2hhj1vhvW2mMuTpSB6AoiqLkTUEz+Q9z2fcBcAXQHzgBfGyMKWeMKQNMAc4FHgGqAJONMcXDEK+iKIpSCM4o8tbafsAr2fcZY5oAjYAPrLUjgWHAeUAPIAUR9lHW2lHA20AtoENYI1cURVHOSFFr8rX8253+7Q7/tvYZbvsDxpg0Y0yGMSZj3759RQxHURRFyY1wDbyaIt6GtXa0tTbBWptQqVKuHUCKohSSoUMhPf30fenpsl+JL4oq8lv92+r+bTX/dssZblMUJQo0awa9egWFPj1drjdr5mxcSvQ5Y5+8MaYL0MB/tYYx5h5gAbAGuMUYsw64HziIDLgeBfYC9xtjDgJ3A9uA+eEOXlGU3ElMhLFjoWtXuOUWmDYNJk2S/Up8UZBM/lHgef/fVwFvAW2A24BNyKBrKaCXtXa/tfYo0BM4BAxHBL+ntTYrzLEripILK1fCX/4i4n7wILz1Ftx/vwp8vHLGTN5a2yGfm1vl8T8LgYZFjElRlEJy8CB8+CGMHg0ZGXDWWdCuHcyfD8ePw6hRIvIq9PGHznhVlBgmkLVfdBGkpcHRo/D66/DRR7BiBTz/PFgLDz98eo1eiR9U5BUlxgiUYJo1g6ZNYfx46NEDliyBNWvgwQdhwwapwf/1r1C2LOzZI9eXL3c6eiXaGDet8ZqQkGDVoExRcmflSinHvP8+HDoEDRrAfffB7bdD+fJ5/1/nzrB1qwi/4k2MMSustQm53eYqF0pFUU4nt1r7zTdLaaZlSzD5zkIRkpJgwADYsQOqVz/z/RVvoeUaRXEhedXad+2Cd9+FVq0KJvAAycmynTs3cvEq7kUzeUVxCTmz9jJlJGu/776CZ+250aABVK4sIn/nnWENWYkBVOQVxWFyq7W/9prU2s8/P/THN0ZKNnPnSqdNUX8slNhERV5RHODQIfjgg/Bn7XmRlAQTJ8LatdBQZ7DEFSryihJFVq2CN9+MXNaeF0lJsp07V0U+3lCRV5QIE+2sPTdq1IDLL4c5c+CRRyL/fIp7UJFXlAjhVNaeF0lJ0plz/DiUKhX951ecQVsoFSWMHDoUnI169dUwbhykpgZno/bt64zAg7RSHjkCy5Y58/yKM6jIK0oYWLVK+tqrVg32tb/2mvS1jx1buL72SNGhAxQrpv3y8YaKvKIUETdn7blRrhw0by51eSV+UJFXlEISC1l7XiQlwbffwv/+53QkSrRQkVeUAhBrWXteJCfDqVPiM6/EByryipIPsZy150bLlmI9rCWb+EFbKBUlB27oa48UpUpB+/Y6+BpPaCavKH5WrZK1UAPOj7//HttZe14kJ8OmTfDf/zodiRINNJNX4ppDh8T58c03T8/a09K8I+o5CVgczJunrpTxgGbySlySPWu/994/Zu2tW3tT4CFoPax1+fhAM3klbojHrD031Ho4vtBMXvE88Zy150VyMuzdK9bDirdRkS8knTvDsGGn7xs2TPYr7uHQIRgzJtjXPnYs+Hzw9deQmRk7fe2R4tprZaslG++j5ZpCkpQEAwdKZ0K1auIFMnAgvPSS05EpIFl7YJWlgwehfn1nnR/dSsB6eO5c6N/f6WiUSKIiXwBOnYL162HRIlixAs47D159VW4zRgRevyjOobX2opGcDO+8o9bDXkdFPheOHRMxX7QIFi+WU/zffpPbLrwQrrsOli6FHTskk7/+emfjjVc0aw+NpCQYMUKsh9u1czoaJVKoyCNmTUuXBkX9229l+jrIKa3PB9dcA23bQu3a8MorMHmy1HuXL5dscfVquU2JLJq1h48OHaB4canLq8h7F2OtdTqG/09CQoLNyMiI+PPs2iViHhD1NWukJFO8uAzStW0rot6mjfQTZ2fYsGANvn9/GDQIXnxRMsfMTKnTK+Ent6z9vvs0aw+V1q2ljXLpUqcjUULBGLPCWpuQ220xnckPHSrZdGJicF96umTXgwbJdWtlCnd2Ud+yRW4rW1ayv8GDRdRbtIBzzsn/OefOPb0GP3So1DRHjJAa58KFULFi+I81Hglk7aNHy3uqWXv4SUqC556Ts9ly5ZyORokEMZ3Jp6dDr14waZIIfeD6kCHSC714sVz27ZP7V6wYLLtccw00bgwlS4Yn9vnzISVFMsyvvpLBWaVoaNYePRYuFMOyadOgWzeno1GKSn6ZfEyLPIiw9+wpQrB0qZRcAvX02rVPF/XLLots9vfZZ/JFad0avvhCzhSUgpFb1t6rl4i7Zu2R4/hxuOAC8bAZMcLpaJSi4tlyDUgG37o1zJwJFSrArbcGhf2ii6IbS5cu8N57cNtt0KMHTJ+urWlnQjtknEWth71PzIt8erq0OIJk8D7f6TX6aHPLLXDggGSgd9wBEyfK2YUSRLN2d5GUBJ9/LhP8atRwOhol3MS0rUGgBj95MjRtKh/QXr1kv5OkpUnHzaRJsqqQiypijpLTQ+bIkaCHzLhx8ekh4wYC1sOazXuTmBb55cuDg64+H2zcCCNHyn6nGTgQnnhC/FMGDoxfoQ94yDRvHvSQ6d5dPWTcRIMGUKWKirxXCVnkjTEPG2O2GWOOGWO2GmP6+ve3Mcas8e9faYy5OvRwT2fQoGBpJjVVtnv2BNsnnebZZ0XEhg2Df/7T6Wiii2btsUNO62HFW4Qk8saYS4FXgFNAf6Ak8JoxpgYwBTgXeASoAkw2xkSsOn355VCvHkyZEqlnKDzGiMdNnz7w5JMwfLjTEUUWzdpjl6QksR7OzHQ6EiXchJrJB/5/JzAX2A0cA1oiwj7KWjsKeBuoBXQI8fnyJTVVJjzt3RvJZykcxYrB22+L2D38MLz7rtMRhZ/VqzVrj3W0Lu9dQhJ5a+0m4HGgDbARaAKkAYEx+p3+7Q7/9g/uLsaYNGNMhjEmY19g1lIR8fnEnmDGjJAeJuyUKAEffCAzYu+5RwaKY51Dh+THq3lzaNJEs/ZYp3p1uOIKFXkvEmq5phLQF1gNdAO+A0YAOc0B8szjrLWjrbUJ1tqESpUqhRIOjRrJBCg3lWwClC4tswpbtpQ++i+/dDqiopE9a7/nHs3avURSEixYIC6sincItVzTAagGTLXWzgCmInX4Df7bq/u3AduuLSE+X74YI9n8vHmwf38kn6lonH22zIqtV0+y3sWLnY6oYGjWHh8kJcmP9rJlTkeihJNQRX6rf3u7MeZuoLf/+mZgL3C/MeZ+4G5gGzA/xOc7I6mpcPKkzIB1I+XLw+zZ0tPfpQusXOl0RHmTM2s/fFgGjzVr9yYB62Et2XiLUGvyGcAAoDQw0r990Fr7HdATOAQMRwS/p7U2K7Rwz0zz5iJKU6dG+pmKTuXK8kUqVkxaQDduDN6Wni7Olk6RV9a+eLEs+tyvn2btXqVcOXnfVeS9Rch98tbaYdbaWtbaMtba2tbakf79C621Da21pay1Tfw/CBGnWDEp2cyaJYLlVmrUkKz44EHx2tm2LTiDt1mz6Mdzpqy9TRvN2uOBpCRZNMeN5U6laMS8d01u+HziqDdrlhiFuZU+fcQFMC1NZh2eOAHXXiuZ1Jo1MgsxcKlcWdwCixXhZzkv3/3Fi0XU33zzdA+ZtDQtxcQrSUkyiW/+fLUe9gqeFPlrrhHv+ClT3C3yIFnzsmVSIqlSRTLq2bMhK5fCVokSUKlSUPRz/ghk/7tSpaBXfrNmp/vuv/WWlF2MEd/9evUka7/jDi3FxDstW0qDwNy5KvJewZMiX6IEdO0KH30kzpRlyjgdUd6kp0tf/+DB8J//SD99+/bw668yqWvPHrlk/ztwfdMm+Tvgn5+TChWCot+gAXTuLGcDu3bJD8Ctt2rWrpxOwHp4zhynI1HChSdFHqTL5u23JSO54Qano8mdnCtbJSaefr1iRcmy88NaGXvI+QOQ29+nTonAX3+9/Jho1q7kRsB6+Mcf4eKLnY5GCRXPinzHjrIE39Sp7hX57C6aINtJk2R/QT3xjYFzz5VL3bp53y/wg3L//XLGsHq1s777intJTpbtvHlw113OxqKETswv/5cft98uy/Dt3h2+tVxjkbzWws3+A6MoAayFqlWlCeD9952ORikI+S3/F9N+8mfC55Pa9sKFTkfiLPmdMShKTrJbD5865XQ0Sqh4WuQ7dYKzznKnl000ye67HyAx0T2++4r7CFgPr13rdCRKqHha5MuWhZQUMQbTjERRCo5aD3sHT4s8SJfN7t2wdKnTkShK7BCwHtZWytjH8yLfpYsMurrZy0ZR3EhSkoxnqfVwbON5kS9XTlrCpkzR9SsVpTAkJ6v1sBfwvMiDdNls3y6LSyuKUjDatxfrYS3ZxDZxIfJdu8qHNd67bBSlMKj1sDeIC5GvWFGyEq3LK0rhSEqS+RRqPRy7xIXIg5RsNm6E9eudjkRRYofkZGk/nj/f6UiUohI3It+9u2w1m1eUgtOihVgPa10+dokbkb/oImjVSuvyilIYAtbDWpePXeJG5EEmRq1eDVu2OB2JosQOycmwebNYDyuxR1yJvM8nWy3ZKErBUYuD2CauRL5WLWjSREVeUQpD/fqywpiKfGwSVyIPks0vXQo7dzodiaLEBmo9HNvEncinpsp2+nRn41CUWCI5GfbtU+vhWCTuRP7KK8VdT7tsFKXgXHutbLWVMvaIO5EHyeYXLICff3Y6EkWJDQLWw1qXjz3iUuR9PqktzpjhdCSKEjskJ6v1cCwSlyLfpAnUrKldNopSGJKSxHpYF+CJLeJS5I2RbH7OHPjf/5yORlFig4D1sJZsYou4FHmQuvyJE/DZZ05HoiixgVoPxyZxK/ItW0LVqtployiFITlZrYdjjbgV+WLFxJnyiy+kzqgoyplJSpKmhfR0pyNRCkrcijxIXf7332HWLKcjUZTYIGA9rCWb2CGuRb59e7jgAu2yUZSCUqoUdOigIh9LxLXIlygh67/OnKm9v4pSUJKS1Ho4lohrkQfpsjlwAL76yulIFMX9DB0K550nfwey+fR02a+4k7gX+aQkOPdc7bJRlILQrBk89hicf76IfHo69Ool+xV3ErLIG2PKG2PGG2P2G2MOGWMW+ve3McasMcYcM8asNMZcHXq44ad0abjhBrE4OHnS6WgUxd0kJsK4cXDokHxnevWCSZNkv+JOwpHJvwP0Bt4GHga+N8aUAaYA5wKPAFWAycaY4mF4vrDj84lZ2aJFTkeiKO5j3z6YNg0GDJDJUDfdJBMJjxyBe+5RgXc7IYm8MaY20B34APgb8K619s9ACiLso6y1o5AfgFpAh5CijRApKVCmjHbZKIq1sgbyuHFw773iPFm5siRCI0fK9+Tmm6Uu/+ijMGaM9sy7nVAz+Xr+bTPgMHDYGPMCIugAgfWXdvi3tUN8vohw9tnQqZOIvK58o3iNoUP/KMSBwdKsLFnc/vXXRbyrV4c6deDOO2HyZKhbF55/HhYvFp+nZ56B2bNl0Z2hQ6VU06uXCr2bKRHi/5f2b88GbgYeAAYBj+W4n8nrAYwxaUAawMUXXxxiOEUnNVU+uN9+K5YHiuIVmjUL1s5btYI33oAnnpC1W597TrrLQAS+fXu45hpo21ZuL5YjDVy+/PQafGKiXF++XMs2biVUkd/q3y6y1k41xlQCOhIU9er+bTX/dkvOB7DWjgZGAyQkJNgQ4ykyN9wAJUtKl42KvOIlAkJ8001SRw+crR45ArfeGhT1Sy4582MNGpT746vAuxdjbdF11RhjgO+AC4EngLuBBKAxMA84AgwF/gEcB+paa7PyeryEhASbkZFR5HhCJSVFJnl8/73YESuKl2jbFr7+Ws5a33wTKlRwOiIlXBhjVlhrE3K7LaSavJVfiFuBH4DXgQuAPtbatUBP4BAwHNgL9MxP4N2AzyeDTt9953QkihJe0tNhzRr5e9684N+Ks+Q3XhIuQm6htNaus9a2staWsdZeZq2d6N+/0Frb0FpbylrbxFrrXIpeQLp2lRqkdtkoXiIwYWn4cLn+l7/oYKlbCIyXBN6LSEwui/sZr9mpXFnqkzr7VfESgcHS228Xg7GsrOBgqeIsiYnw9ttie/73v0dmcllINflw43RNHqSVrF8/2LBBeoQVxUs0biyL5XzxhdORxC+nTsHKlfIezJoFy5YFB8MHD4YhQwr/mBGryXuR7t1lqyUbxYs0bAiZmU5HEX/8/DNMnAh33AEXXijlmKeekpnDZ50ljR6PPQb/+U/4y2gq8jmoXl0WRlCRV7xIw4awcyf89pvTkXibrCzJ0J9+WvSkcmXo3Vsy9+uugwkTYM8eGR85fBj69JFJZ5GYXBZqn7wn8fnkV3XbNqhZ0+loFCV8NGwo28xMaNfO2Vi8xp498OWXIuSzZ8Mvv0gjR4sWIvYpKdC06ekTzEaOFJPEl1+W65GYXKYinwsBkZ82DR55xOloFCV8qMiHj5Mn4ZtvgrX1FStkf5UqMrmyUydZ+Dyv+Qjbt0u7dt++p98n3JPLVORzoW5duOoq6bJRkVe8RLVqUL689skXlV27JFv/4guYMwf274fixcUu4rnnJFtv1OiPdhC58dJLcr8BAyIbs4p8HqSmyinWTz9JN4KieAFjdPC1MJw4AUuWSKb+xRfBiZIXXSRn/CkpsvBQ+fKFe9y9e8XB8/bbZRwwkujAax74fGK7On2605EoSni56ipYu1Y+38of+e9/4a23RAMqVJCFy196SVbDev55EfodO6S/vUePwgs8SKv2sWO5ewGFG83k86B+fbjsMumyuf9+p6NRlPDRsCEcPCg1YW0sELFdvDiYra9bJ/tr1BADt5QU6NgxuLZtqBw4ACNGSLt2NObiqMjngTHyS/7iizJKrmZOilfIPvgaryK/bVtwwHTePGljLFVKBqPvukuE/corI2NUOHq01PIfy2nIHiFU5PMhNVVOz2bOlEUUFMULNGgg28xMuPFGZ2OJFkePwsKFQWHfuFH216oFf/qTdMIkJsI550Q2jmPHYNgwOTNo3jyyzxVART4fmjaFiy+WLhsVecULDB0qsy0vuSQ4+JqeLn3Z0agPR5Pvvw+WYNLT4fffpSe9QweZhNSpk5Rko2krPn68NHOMHx+951SRz4dAyWbUKKlhnnuu0xEpSmgEXA/r1pU2yoDr4aRJTkcWOkeOwPz5QWH//nvZf+mlsuB4SoqsfFW2rDPxZWXJj2zTpnDttdF7XhX5M+DzwauvwmefwS23OB2NooRGYEZlly5SwoiE62G0sFYW+QmUYObPl3LIWWdJOeShh0TY69RxOlJh6lT54fn44+iePagL5RnIypIJJO3aeSPbURSAnj1loe677oJ33nE6moJz6JCcfXzxhVy2bZP9V1whgt6pk3xXy5RxNMw/YK1k8IcPw/r1MoEqnOTnQqmZ/BkoXhy6dRNDod9/lyxBUWKZ9HT46iv5e9IkcUZ0ayZvrYhiIFtftAiOH4ezz5aSx2OPibC7vUtozhxYtUomQIVb4M+EToYqAKmp8gs8e7bTkShKaARq8JMnS12+USP3rRJ14ID4RqWlyQBxgwbw6KNiAPbQQ9Ly+OuvMGOGDKC6XeBBuvQuukhmuEYbzeQLQIcOMtttyhRZIlBRYpXAKlGJibKw98yZ4Xc9LCzWyiBwYMD066/F/Ou888Qy4Mkn4frrZXJSLPLNN/Ij+tJL0t0TbVTkC0DJknDTTZI5HD8ukyYUJRbJ3ibZti2MHSsZZrTbJ/fvlxLGrFly2bVL9jduDAMHSn29VSv57sU6zz8vSWJamjPPryJfQFJTYdw4+UW+/nqno1GU0GnbVraLFkV+ev2pU7B6dXDAdNkyaWooX14W0ejUSS5eMwPcsEH8rwYPdq4FW0W+gCQny2y4qVNV5BVvcNllUKmS+Lbce2/4H/+XX2Qca9Yssefds0f2N20Kf/ubiHqLFlDCwyr0wgvSrNG3r3MxePjlDS9lykhv8fTpMjkq2iPkihJujJFsfvHi8DzeqVOQkRHshPn2W9lXoYJk6ykpkiBVrhye53M7P/4I778Pf/2r/Jg6hYp8IfD54KOPZGBIV9VRvEDbttLJsmuX1OYLy759wUU0Zs+WBauNEV+WwYNF2BMS4jMpGjZMtv37OxuHinwh6NxZRsenTFGRV7xBoC7/9dcyQepMZGVJt0igE2bFCumOqVRJBD0lRUqbFStGNm638/PP4kl/223SBuokKvKF4Jxz5HRz6lSxOojm1GRFiQRNmoiXy+LFeYv87t3BLpjZs+G332TZupYtYcgQEfYmTQq25F288Prr4qUTLTvh/FCRLySpqfDJJ9JXHC2rUEWJFK+8ApdfLh02AebMkUTm/PMlW1+9WvZXrSqzvwMLVJ9/vjMxu51Dh0Tku3aFevWcjkZFvtDceKN0A0ydqiKvxD7NmsEzz4hlxxtvwMSJktVbK3X0Nm3g3/8WYW/USM9eC8Lo0XK28/jjTkciqEFZEbj+etiyRRzw9EOvxDovvywTkEBKLp06wd13izdMuXLOxhZrHDsGtWtLe2o0rSLyMyjTKloR8PnEMnTtWqcjUZTQ6d9fypAAf/+72Gr7fCrwReH996VTyS1ZPKjIF4lu3SSDnzLF6UgUJXTmz4cFC6Tl8Y033GVWFktkZcnkpyZNZF6AW1CRLwJVqkjr2dSpTkeiKKGRfWWoIUNk6zZXylhh+nQp4T7+uLvKuCryRSQ1VdbI/L//czoSRSk62V0pIbhy1PLlzsYVa1grRmR16gRLX25BRb6IdO8uW83mlVhm0KA/WgwnJnpvUe9IM2+eWDoMGuS+2b0q8kXk4oul/Uzr8oqiPP+8zCP405+cjuSPqMiHgM8np7U//uh0JIqiOMXy5ZLJP/KIM4uCnAkV+RDw+WQ7bZqzcSiK4hzPPy+++Pfd53QkuRMWkTfGlDHGbDLGWGPMCP++K40xS4wxx/y3uaipKDxcdpmsP6l1eUWJTzZulCTvgQdkuUI3Eq5M/kmgeo59HwBXAP2BE8DHxhjPTa9ITRXfj8CCCIqixA8vviglmn79nI4kb0IWeWPMVcAjwFPZ9jUBGgEfWGtHAsOA84AeoT6f2/D5pH1q+nSnI1EUJdIMHRqcQ7BjB7z3nticjB3raFj5EpLIG2OKAWOAkUB205la/u1O/3aHf1s7l8dIM8ZkGGMy9u3bF0o4jtCwIdStqyUbRYkHmjULThYbNkxmuS5aJPvdSqiZ/F1ATWA8UM2/rxyQc431POd/WWtHW2sTrLUJlZxcI6uIGCPZ/FdfifOcoijeJTBZrEcPGDECSpaEyZP/ONfATYQq8jWASsB3wAT/vtuBNP/fgTp94AdgS4jP50pSU+HkSZg50+lIFEWJJNbKkodHj8KJE3DXXe4WeAhd5CcBPf2Xp/37ZgGDgDXALcaYB5DB14OAJ6cOJSRA9eo6MUpRvMzu3ZLQ3XwzHD8uLZOTJ7vf5yckkbfWrrfWTrbWTgYW+Hf/YK1dAdwGbEIGXUsBvay1+0OK1qUUKyYlmy+/lFVhFEXxDtbC+PGyytOnn8LZZ8uKWW+8ERuGbmGbDGWtnW+tNdbaB/3X11lrW1lrS1trL7PWzgrXc7kRn08WDPj8c6cjURQlXPz3v9Cli9gVXHklPPSQlGWTkuT2WDB00+X/wkTbtrJi/dSp8suuKErsYi2MGQMDBkgHzfDhMuEpN/OxxER31+XV1iBMFC8ui4l89pkMyiiKEpts3SoLlaelyXhbZqZMdnKbu2RBUZEPI6mpUpOfM8fpSBRFKSynTsHrr4tVybffSs197lxZszWWUZEPI4mJsi6mdtkoSmyxeTO0by8Z+zXXyPrN990nTRWxjgcOwT2UKgU33QSffCI9tIqiuJuTJ8V/plEjEfaxY6Vz5uKLnY4sfKjIhxmfT2a+zp/vdCSKouTH2rXQurWs5nT99bB+vXTRuGl91nCgIh9mrr8eypZVLxtFcSsnTsA//wlXXy2DrB9+KHbBVas6HVlkUJEPM2edBZ07y4cmK8vpaOKX7G6BAdLTZb8Sv6xaBc2bw+DBcta9fr3MYPVa9p4dFfkIkJoq/vJLlzodSfyS3S0QZNurl7vdApXIcewY/OMf8v7v3i1n2h9+KHNbvI5OhooAnTvLIOyUKTJJSok+iYnwzjuQkgJNm0r3xKRJ7p60okSGb76BP/85WHMfNgwuuMDpqKKHZvIR4Lzz4LrrJFuw1ulo4pNt2+Dxx8VIaskS2XfOOY6GpESZI0dg4EAZXD1wQCxHxo6NL4EHFfmI4fPBjz/CihVORxJ/ZGRAy5awfbv84N52G/z6q+x74gk5dVe8zcKF0hb58stw772wbp2c1cUjKvIR4qabZBq0dtlEl08+kUktICWzadPg/fdlecaSJeFf/5K67KpVzsapRIZDh6BvX/kMZGXJjNU33nDvItvRQEU+QlSoAB06SF1eSzbR4fXXxT+oXj3J3qZMCdbgb7xRJrnceacs+tC8OTzzjE5a8xJz58pynCNHyszVNWvg2mudjsoFWGtdc2natKn1EqNGWQvWrl3rdCTe5uRJax9+WF7rrl2tPXQo//v/8ou1vXvL/Zs0sXbNmujEqUSG/futveceeT8vu8zaRYucjij6ABk2D13VTD6CdOsm/bfqZRM5jhyR9TZffVW8vqdMkUUd8uOCC2DCBCml7dgh3RA729cAABB7SURBVDf/+pdMcVdii88+g/r1pZNq0CBYvVo72nKiIh9BqlaVkX2ty0eGPXukJDZjhvh9v/pq4exgu3eXAblu3WRAtnVr2LAhYuEqYeSXX+COO+CGG6B8eVi2DF54QSYjKqejIh9hfD747jv44QenI/EWGzZIt8zatTK42q9f0R6nUiXpn//oI9iyBZo0EcMqna3sXqZMkXGXDz+EJ5+UDjad5JY3KvIRxueTrWbz4WP+fMm6f/8dFiyArl1Df8xevYJtdoMGid3s5s2hP64SPvbuhZ49pTxXrZosuffMM1C6tNORuRsV+QhTs6YYIWldPjy8955MNKtaVU7Rw5nBVakiP8YTJsiZQuPGUgY6dSp8z6EUHmth4kTJ3j/5BJ57TmaxNm7sdGSxgYp8FEhNlQ/ljh1ORxK7WAtDhkCfPjKwtmSJ/ICGG2Ogd2/J6hMT4eGHZbtlS/ifSzkzO3fKmVrv3lC3rsxv+PvfZc6DUjBU5KNAaqpsp01zNo5Y5fhx8R556ikR+VmzZLAtklx0EXz6qXRtrF4NV10Fo0ZpVh8trJXXvn59WU7z5Zfh668lm1cKh4p8FLj8cvlwal2+8OzfL3XysWPh6adlW6pUdJ7bGLjrLhncbdMGHnhASkXbt0fn+eOV7dtlXYa77xZrgjVroH//2F1I22lU5KNEaqr4aezb53QkscP27SKuixbBuHGSyTvh+12jhpw9vPmmlN0aNoQxY3Qmc7g5dUrOlho0kHLcyJFiEX3ppU5HFtuoyEcJn08+xDNmOB1JbBAwGdu5UwS2Tx9n4zEG0tIgMxMSEsQ2ISVFx1nCxfffQ8eOcrYUaI3961+9sZC20+hLGCUaNYLatbXLpiDMnCkGU6VLS0bXsaPTEQWpWVM8Ul5/Xc4wGjSQswzN6otGVha88oqMeaxaJWdIs2dHZlA9XlGRjxLGSDY/b57UmZXcGTEiaDK2bJk7B9qKFYMHH5RJbg0biulZ167w009ORxZbbNggnVL9+4uR2Pr1Uof38lJ8TqAiH0VSU8X18NNPnY7EfWRlwSOPiE3sjTfKhKcLL3Q6qvypW1fiHDZMOkDq15d+bs3q8+fkSfj3v6XPffNmmZfwyScywUkJPyryUaR5c2nN0y6b0ymKyZhbKF5cfpxWr5Yuqt695Vj27nU6Mnfy3XfQooX0ut90k2TvvXtr9h5JVOSjSLFiUrKZNQsOH3Y6GnewZ49MNpoxQ0S+sCZjbuHyy2HxYjHJ+vRTyeonT3Y6Kvdw/Lh0RyUkyGD1xx/LpUoVpyPzPiryUcbnE8+VWbOcjsR5AiZjmZkyUeyhh5yOKDSKFxffm5Ur4ZJLxGflllvEMTGeycgQO+chQ+DmmyV779HD6ajiBxX5KHPNNVCxonbZBEzGjhwJn8mYW6hfH5YuhWefldJc/frx2Tp79Kgspt6ihayx+8knUn+vUMHpyOILFfkoU6KECNqnn8bvgtITJgRNxr75xps2sSVLwj/+IU6JF14oHUN9+sBvvzkdWXRYskQGVl94QWYNr1snA+pK9FGRd4DUVDh4UPqt4wlrJbu94w6Zyfr1197vh27UCL79VnzPJ06UvvrPP3c6qshx+LCYurVtK5n87NnS+x5pryElb1TkHaBjR1k9Pp66bAImY08+KSL/5Zdw/vlORxUdSpUS3/NvvpFj7tJF+sH/9z+nIwsv6ekyqWn4cJmtmpkJyclOR6WoyDtA6dJy6jpjRnysK7p/P3TuHDQZGzcueiZjbqJpU1nF6G9/k9eiYUPpr491DhyA+++X5KVYMRljGTECzj3X6cgUCFHkjTGXGmPSjTG/GGMOGmPmGGPq+G/rZoz53hhz1Bgz3xhTKzwhewOfT7ouFi50OpLIsn27nLovWCDC5pTJmFsoXVoWDV+yBMqWlbGJv/xFynexyKxZUoIaPRoGDJA++HbtnI5KyU6omXw1/2M8BbwLJAFjjDEXAh8CB4BHgabAuBCfy1N06iSLDnu5yyZgMrZjh5Rn/vQnpyNyDy1aiFfLgAEikFddJeWOWOG332RANSUFzjlHxldeekl+uBR3EarIL7HWtrfWjrDW9gN+BeoDtwKlgX9ba18HpgHXBLJ8Rb4MKSnSH+7FhSjcbDLmFs46S4Rx0SLpuurYURYkd/tEuRkzxFPovfdk5urKlfJjrriTkETeWns88LcxJgG4AFgIBEozO/3bgCFr7ZyPYYxJM8ZkGGMy9sWZ2XpqqphaLVvmdCThJRZMxtxEmzZii9Cvn7hbNm4ss2fdxr59cOut8t5WrixdQ889B2XKOB2Zkh9hGXg1xlwBfAJsA/rmdpe8/tdaO9pam2CtTahUqVI4wokZunSRfmqvdNlkZYmjYN++cMMNsWEy5hbOPlu6UtLTZTC+XTsp5fz+u9ORSevrRx/Jj/WUKTJzdflyWaBecT8hi7wxph4wHzgOdLTW/gRs9d9c3b8N+MvpcsjZKFdOWsymTIl958IjR2Qa/yuvSEY6dWrsmIy5iQ4dpPXwvvvE3bJJE2m9dIqffpIzzltugVq1pDQzeHB8dkfFKqF219QA0oGKwBtAC2PMLcig63HgMWNMX6A7sNha+0OI8XoOnw+2bZPT9VglYDI2fboYjA0fHpsmY27hnHPgP/+RiURHjoj9w9/+Ft0Z0tbC+PFiyfD55zB0qIytNGgQvRiUMGGtLfIF6ADYnBf/bT7gB+AYUqevc6bHa9q0qY039u2ztlgxa594wulIisaGDdbWqmXtWWdZO32609F4j/37rb37bmvB2vr1rc3IiPxz/vijtSkp8pxt2li7cWPkn1MJDSDD5qGroQ68zrfWmpwX/21TrbV1rLWlrbXtrGbxuVKxonShxGJdfsECaNVKukG8ZjLmFsqVE1uAzz+XtsUWLWTW8PHjZ/7fwmKttHPWry/v5/DhMo/j8svD/1xK9NAZry4gNVVsdzdscDqSgjNhgownVK0qHTReNBlzEykpsrh1797i/9O8uUw8ChdbtkBSkowFJCTIuEC/frqQthfQt9AFdOsm21jI5nMzGaulc5mjwvnniyXE9Omwe7eI8bPPypKSReXUKWnbbNhQOmbefFPWIa79h2ZnJVZRkXcB1apJ2cPts19PnBBjrXg0GXMTXbuKdW+PHvJetGol1wvL5s3Sqtmvn5QM162DtLT4tp3wIiryLsHnk2nuW7ee+b5OsH+/lAzefVf8Z+LVZMwtVKgAH3wgS+ht3y496y+8UDDDu5Mn4cUXxQZ53Tp5Lz/7DGrUiHzcSvRRkXcJPp9s3ViyyWky9vTTmu25hR49RKhvuEFWYWrbFjZtyvv+a9dKS+agQeKftH69LGai76d3UZF3CbVry3R2t4n8ihVqMuZ2KleWRcMnTpQSTOPGIvrZF6U5cUIMxRo1krPFjz6Sz1rVqs7FrUQHFXkXkZoqE0527XI6EmHmTKnZqsmY+zFGfGXWrZOup88+k/LahAlSBrzySjkLa99esvdevTR7jxdU5F1EYP3P6dOD+9LTZbZhtBk5Uk3GYpGqVcUlctw4+XG+4w5ZrGTLFvGc+eoriDOLqLhHRd5F3HCD2AGMGSPX09Ml44pmD/qpU2KM9eCDajIWqxgjdfZNm+CKK6TtdcAA8ZxR4g8VeReRmAg33yyn1336iOHXpEmyPxoETMaGDVOTMS+weTP8/LOI+9ixsbUoiRI+jHWR/WFCQoLNyMhwOgxHycyUVYIC1KwpE1Wuuiq4vfRSWWQinOzdK+vOLl8uTpIPPRTex1eiS+AsMJAk5LyueAtjzAprbUJut4VZKpRQ+flnuOACGTybOVNE/ocfxLskK0vuU7q0DKRlF/6GDaWsUpTBtI0bZaHt3bslew/MwFVil+XLTxf0xES5vny5iny8oZm8i8gv+2rdWrxtMjNhzZrg9qefgv9fsaKIfXbhr1//9JLL0KFS4w980RcskNq7tTIo17x5dI9ZUZTQ0Uw+RjhT9tW4sVyy88svfxT+MWOkvg6S2depExR9Y6RVc9Ik8YEP9L2PH68CryheRDN5D3LqlEx4yS78mZnwf//3xxWoSpaUiTQ33eRMrIqihI5m8nFGsWKSvdepA927B/cfOSITYTIzxW3wm29g4EAVeEXxMtpCGUeULSv2tIHB3MGD4a23tLVOUbyMinyckX0wd8gQ2fbqpUKvKF5FRT7OyG9wV1EU76EDr4qiKDFOfgOvmskriqJ4GBV5RVEUD6MiryiK4mFU5BVFUTyMiryiKIqHcVV3jTFmH7AdqAj87HA4ThPvr4Eevx6/Hn/BucRam+uaX64S+QDGmIy82oHihXh/DfT49fj1+MNz/FquURRF8TAq8oqiKB7GrSI/2ukAXEC8vwZ6/PGNHn+YcGVNXlEURQkPbs3kFUVRlDCgIq8oiuJhXCfyxpg2xpg1xphjxpiVxpirnY4pUhhjLjXGpBtjfjHGHDTGzDHG1PHf1s0Y870x5qgxZr4xppbT8UYKY0wZY8wmY4w1xozw77vSGLPE/znYZIy5zuk4I4ExprwxZrwxZr8x5pAxZqF/f1x8D4wxDxtjtvmPc6sxpq9/v2eP3xjzmjFmj//z/mm2/Xl+5kN5PVwl8saYMsAU4FzgEaAKMNkYU9zRwCJHNeQ9eAp4F0gCxhhjLgQ+BA4AjwJNgXFOBRkFngSq59j3AXAF0B84AXxsjCkX7cCiwDtAb+Bt4GHg+3j5HhhjLgVeAU4h73NJ4DVjTA28f/wf5rIv1898yJ8Ha61rLkB3wAKP+q8P8V+/1unYInS8pXJc/wXY638jLdDTv3+8/3odp2OOwGtwFfA7MNB/jCOAJv6/R/rv82f/9budjjfMx17bf1wTgFJAcf/+uPgeAJf7j2uR/+8M4CjQ0+vHD9T0H9On/ut5fuZD/Ty4KpMHAiWJnf7tDv+2tgOxRBxr7fHA38aYBOACYCFx8joYY4oBY4CRyBc8QFwcP1DPv20GHAYOG2NeIE6O31q7CXgcaANsRIQuDajhv4unjz8H+b3nIX0e3CbyOTFOBxANjDFXAJ8A24C+ud0lqgFFj7uQjGY8UroCKIectmfHq8df2r89G7gZ+BoYBJTIcT9PHr8xphLyeV8NdAO+Q87kzsl51yiH5gbyO+ZCvR45P0xOs9W/DdRnA1/8LQ7EEhWMMfWAr5DT1I7W2p+MMfHyOtQAKiFf7gC3Axf5//b68Qfe50XW2ql+0etI8Evs9ePvgBzbG9baGcaYhsCzwAb/7V4//uzk953/NZ/bzozTtakcdaoywB7/Ad+PnJ5sxV+r9NoFEbk9wEnktPUW/6UqcAxYgWQ6BxEhcDzmMB9/PaCH//IUUmf8Ahlo/s7/4X4AWIsMQpd3OuYwH78B1iDjMPcCy/yfhQbx8D0AEvzv+Uak9rzBf72Rl48f6AI85j/W74B7gEvz+syHqouOH3AuL0A7IBM4DqwCEpyOKYLH2sH/Rp928d/mA37wi/1CPDjomsdrMcJ/vT6w1H/8m4FOTscYoeMOHOdR/3He5t8fF98DpJNkq//4twAPeP34gfm5fO/vzO8zH8rrobYGiqIoHsbtA6+KoihKCKjIK4qieBgVeUVRFA+jIq8oiuJhVOQVRVE8jIq8oiiKh1GRVxRF8TD/D5zv3BPm1eKCAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_solution(cities, tour)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plt.plot(t, t, 'r--', t, t**2, 'bs', t, t**3, 'g^')\n",
    "from scipy.stats import sem\n",
    "\n",
    "def plot_learning(iterations: int, lengths, disp_iter=1000):\n",
    "    bin_size = int(iterations // float(min([iterations, disp_iter])))\n",
    "    errors = np.reshape(lengths, newshape=(-1, bin_size))\n",
    "    iters = np.reshape(list(range(iterations)), newshape=(-1, bin_size))\n",
    "    plt.errorbar(\n",
    "        iters.mean(axis=1),\n",
    "        errors.mean(axis=1),\n",
    "        yerr=sem(errors, axis=1),\n",
    "        fmt='--o',\n",
    "    )\n",
    "    plt.ylabel('distance')\n",
    "    plt.xlabel('iterations')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "findfont: Font family ['normal'] not found. Falling back to DejaVu Sans.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYcAAAEHCAYAAABFroqmAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df3hcdZn38ffdMKVTfjQgEe3QUkApCoUG4wKyKuBKnxXRUMDya11RRFmUi+JGyy48FBZtH+sK8iysFygXurBQKBCBigX5IT5gxdS01K50lR8FAgsBGix02k7T+/njnGknycxkfpwzk2Q+r+vqNZkz55z5njade873/n7vr7k7IiIiucbVuwEiIjLyKDiIiMgQCg4iIjKEgoOIiAyh4CAiIkMoOIiIyBA7xXViM3s/cD1wKDAeWA58FXg38K/AB8NdHwK+6u694XFfAS4F3gU8AHzR3d8o9l577bWXT5s2LYarEBEZu1asWPG6u7fkey224ACkCO5MLgMOBL4O/Ai4CXgd+BbwceB04C/A2WbWCvwQ+CXwIPAd4Crg88XeaNq0aXR1dcVyESIiY5WZrSv4WlyT4MxsvLtvyXn+BtAP7JPdbma7EQSG37n7X5nZD4ALgL9y99+Z2WPAUcBu7r6p0Hu1tbW5goOISHnMbIW7t+V7Lbacw6DA0AbsCTyWux2YFT4+Fj7uFz72hI8vEdzdTImrnSIiMlTsCWkzOwi4B3ieoGspu/1o4EZgBTC/0OFFznuumXWZWVdvb29k7RURkZiDg5l9EHgU2AIc5+6vhNs/BvwCeAaY5e5vh4c8Fz7uEz6mgK3Ai4PP7e7Xu3ubu7e1tOTNp4iISIViCw5mNgV4BNiLIMl8hJmdZmaHA/cDTcANwCfN7MTwsJ+Gj982s28CHwFuK5ZvEBGR6MU5WukAgmGrAAtytp8NTAx/vjZ8XAfc6+4rzOx84J+BjxIEkbkxtlFERPKILTi4+6MUzhncVOS464DrYmiSiIiUSDOkRURkiDi7lca0zu4evrnkKbb0byPVnKRj1nTaW1Mj9rzlvP+iZWt5uS/N5Dq8v4iMDAoOJRj8gXnsQS3cuaKHLf3bAOjpS3PxXasBhnyQlvNh29ndw8V3rR5y3q51b/LI070D3j/3eZSB6eK7VpPO9A97XSIytsU2Q7qWqp0hnfttvTmZwAz6NmYGBILsB2YxzckEu+y805AgUujYPSYmuOzEg7d/8B698GF6+tJD9jOg2L9SYpyx64Sd6NuYYVIywdubt7J1m5d951Ho/YG63MWISLyKzZBu6ODQ2d3D/HvW0JfOFNxnuA/mYso5NtWcLPjBXI1kookFs2fQ3poaEASbzOj3gQFkv3lLi7Y391wiMvopOOQxuAulkRnwkQP2ZPmz6+kf5vch1Zzk8XnHbX+uHIXI6KXgkEexLhQp7uo5M2lvTXFJ52puXv7CsPsP7pLKDSiTBnXjKbiI1E6x4NCwCemXFRgqduHilXzj9pX0l/i9Ijex3bXuzQEBJbdLr6cvTceSVUDhBHi9R3OJNIqGvXNoveIB1m8snGuQ+moelFg/9qAW7lv1ypD8kPIgIpWrS8nukW6Tcg0jWl86w9ZtwReXnr40Ny9/Ie/AgXSmn0XL1ta6eSJjXsN2K6Uz2+rdBIlItotQXU4i0WnY4CBjhwMzL3+Ad7ZsJdO/424jdwKfRlWJlKdhg8MeExPKOYwhw3U5aea3SHkaNudw2YkH17sJUgMv96VZtGztkPksylWIFNewdw7SGCY3JwsOW+7pS3P0wofV1SSSR8MGB31rbAwbt2wtWBLEYPtEyHw5CiW3pZE1bHDQJLjGUCivlK/uVTrTz9zFK+la92bJVXdFxqqGzTlMbk5WdfweExMRtUTqodDdhAM3L38hb47iwsUrOXrhw3R298TePpF6a9jg0DFrOslE04BtyUQTV8+ZWXBt06zmZILu/308zy88oep2pJqTXD1nJlfPmUmqOYlReG3VfO1oTpYfpEo9vwyVvYtQgJCxrmG7lbLdA/nGvi9atrZgUb5koon5n9kx0qnSIbGDq5vmtqmUirHZdmT7xzvuWEVmW/7vwwaceeRUrmyfsf38gxcvyleaQvLLjnRSF5OMZQ1bW6mYQh/Ogxfnye7bsWTV9slXpSilHlC+D/Biq79FUek0e458gXEcgEGB+NNwDHguvHPUBDsZrVSyuwLlLu85eF+g5AAzEhW6psGLI2VzL4XunnJH+kybtzT+htdQqsBqfyoGKKNFXYKDmb0fuB44FBgPLAe+6u7PmFk78D1gn3D72e7+XHjcV4BLgXcBDwBfdPc3ir1XHMEhCo3yjTLfnVa+D8ixuIZGodX+8nUbiow09VrPIUXQG3EZcCDwdeBHZnY6cBvwX0AH8B3gJ8DHzKwV+CHwS+DB8LWrgM/H2M7YtLemxmQwGKxY/iZXx6zpQ4JIYpyBMaBbLt+2kapQCzVUWka7OIPDE+7+8ewTMzsTOBg4HdgZWODud5jZh4G/M7MDgC+Eu/+Tu//OzD4NnG5m57r7phjbKlUqJRAWCiKlbBttdxzjzOjs7mmILwcyNsUWHNx9S/ZnM2sD9gTuBPYLN2fHAr4UPu5f4LWdgCnAn+Jqq9ROoSAy3LbR1iXV787cxSu5cPFKzbCWUSn2eQ5mdhBwD/A8QdfSkF2KHV7kvOeaWZeZdfX29lbXSBnx8s1LGemyXU6aGyGjUazBwcw+CDwKbAGOc/dXgOfCl/cJH7Nfp54t8NpW4MXB53b36929zd3bWlpaYmi9jCTtrSkWzJ6xfaJgczJBoqn4dL5KJgjGRVVgZbSJrVvJzKYAjxCMOroEOMLMjiBIRi8EvmVmewMnAf8vHMX0U+AC4Ntm9iDwEeBW5RsEhnZJdXb3cOHilXn3NWDlZcePqO6okdIOkVLEeedwAPBuoAlYANxK8EH/CkFSuplgOGs3YSLa3VcA5wMfBK4A7gfmxthGGcXaW1OkCtTIytbOGkndUU2mwiUyesQWHNz9UXe3wX/C1+5y9wPcfWd3/5i7P5Nz3HXunnL3Ce5+oru/HlcbZfQrVCMrO+IpX3fUuDp9Rve7K+8go0bD1laSsaGUORb5uqPm3r6SehQHUOlvGS1UPkMaUinFDZuTCd5KZwpOdKvWaCmlImNXsRnSDVuyWxpbbncTDB0zna16W+26H8Ws35jhwsUrab3iAXU3yYijOwcRCtfBKjYiKkqJcYYDW7e5Js1Jzagqq0gVWq94oKI1O6qhyq5SC+pWEqnCZSceXPPhsJo0J/Wm0Uoiw8gdEVXLiWyq7Cr1pDsHkRK0t6Z4fN5xJa0xHpU4k+Eiw1FwEClDe2uKM4+cGnmAGDwxL3cin0g9KDiIlOnK9hlcNWfm9lnXqeYku4yvLCex9+47c/WcmZxxxNTt5TWazDj5Q42xUJSMXBqtJBKBaoa8NhkUWvROw1olThqtJBKz9tYUZx05taJji62G2tOX1kQ5qQsFB5GIXNk+I7Zzr9+Y0YJBUlMKDiIRKlRCPAqa+yC1pOAgEqG414/Q3AepFU2CE4lQ3BPmNPdBakV3DiIRy50wF+VdhOY+SC3pzkEkJpXeRZixfSGiieObSG/pz7uIkUicdOcgEqPsXUQ5iercqUe77Kzvb1IfCg4iNdAxazqJChav7t2wGSeY76ChrFJLCg4iNdDemmLRqYfRnExUfA4NZZVa0j2rSI20t+6ol9TZ3cPcxSvLXp+6liXDpbHFeudgZteY2atm5mZ2X872M8xsrZltMrMeM7sy57UPmNkTZrY53Of4ONsoUg+VVnc1UNeS1EQtupVuy31iZhOBnwB7Af8IvAn8s5l9NNzlVuAg4CIgA9xhZpNq0E6RmrqyfQZnllmPyYH596yJp0EiOWINDu5+AXDVoM1NwDaCoPBL4Plw+1tm1gocBtzq7tcC3wd2B06Js50i9dDZ3cOSFS+VfVxfOsMlnatjaJHIDjVPSLv7BuBLwL7AH4FPA5e4+1PAfuFu2fvm7P+c/Qefx8zONbMuM+vq7e2NudUi0Vu0bC2bMtsqOvbm5S+oUqvEqubBwczGA98CXgFOBh4ALjOzfDXFC3bJuvv17t7m7m0tLS3xNFYkRtXWSVKlVolTPUYrHQYcAvzY3e8KcxDHA8cSdDMB7BM+ZqeDPlvbJorEb3JzsurRR7nDWxctW8vLfWnNppZIxD1a6QRgTvh0ipmdA0wAtgInmNm5wHnh62vdvRt4CjjNzM4nSEpvAO6Ms50i9RBVBdfsBLmevrQmzElk4u5W6gAWhj8fCtwAHAB8AXgLuIYg93Clu98T7ncGsJYgGT0e+Jy798XcTpGaa29NsWD2DN61y/iqz5XO9A95rglzUo1Yu5Xc/ZgiL99S4Jg1wFGxNEhkhGlvTbHnLuP5/I1PcuC7d2XdmxvZvLWyJPVgWvtBqqHyGSJ19ptn3gDgv197m/FN5ddfKkRrP0g1FBxE6qizu4cbH39u+/MNm/tJJpq4es5MPvr+vSo+b2Kcae0HqYqCg0gdLVq2dkg3UjZfMH3v3So/cXQ3INKgFBxE6qhQXqCnL80dK16s+LyZfldCWqqi4CBSR8XyAm+lt1Z1biWkpRoKDiJ1FNVch3wcVGJDKqb1HETqqNJ1pku1fmOGjiWrBryXSCl05yBSZ5WsM10O5R+kEgoOIiPEcF1MTVb5ECTlH6RcCg4iI0S2nEYh/e5cPWdmZSc3rSAn5VFwEBlB2ltTBbuXsvcNldxAuEPHklUKEFIyBQeREaZj1vS8c9icIHF91H57VnRe5R6kHAoOIiNMe2sKL/BaT1+a7hffqvjcyj1IqRQcREagQl1LTWZDynOXw4Fp85Zy9MKH1cUkRSk4iIxA+UYuJRNN9Huhe4ryaEEgGY6Cg8gIlB25lGpOYgR3EtnnUdGCQFKMZkiLjFDtram8s5ovvmt1VV1LuZSDkEJ05yAyiuTeUUTBQfkHyUt3DiKjTO4dxbR5S6s+Xzb/kD23CJR452BmB5rZQ2b2h/D5oWZ2SbxNE5FiPKLkNCj/IEOV2q10A3AxkAFw96eA0+JqlIgM779ffTvS8yn/ILlKDQ4T3f3JQduGXYnEzK4xs1fNzM3svpztO5vZD8zsNTPbaGbdZtYcvvYBM3vCzDab2VozO770yxFpHG9vrm4xoMGKLTwkjafU4PC6mR1AkL/CzE4BXinx2NvybFsAXADcB3wNeBLIDuq+FTgIuIjgTuUOM5tU4nuJNIwnnnk9snMlE010zJoe2flk9Cs1IX0+cD1wkJn1AM8BZw13kLtfYGbTCAIBAGY2EfgH4HHgy8A4d78xfK0VOAy4zt2vNbM08GPglPBRRAgqrP7bw3+O7HwLZs9QMloGKCk4uPuzwN+Y2S4EH+YbqnjP/YGdgcnA28BOZnYr8EVgv3Cf7Li6l3KOEZHQomVr2bx1WyTnqmadCBm7Sh2t9B0za3b3d9x9g5ntYWZXVvieO4ePLcDZwBLg74Av5HvrIm0618y6zKyrt7e3wqaIjE6FkseVfMz3u6uUhgxRas7hb929L/vE3dcDn6rwPdcR5C7+4O63ATeF2w8g6K4C2Cd8zN7nPjv4JO5+vbu3uXtbS0tLhU0RGZ0KJY8nNyf5xvEHMq7MKKGhrDJYqcGhycyy3/gxsyQ77gAKMrMTgDnh0ylmdg6wB7AUmGlmX2NHPuIxd+8GngJOM7PzCZLSG4A7S2ynSEMoVJjv2INauPaRP7OtgikQPRrKKjlKDQ63AA+Z2ZfM7EvAg8BPSjiuA1gY/nwowXyJo4GvAo8B3wMOAS5y9/vD/c4A1gLfB8YDn8u9axGRwoX5Hnm6l02ZynIRyj1ILit1lqWZ/S3wifDpg+6+LLZWlamtrc27urrq3QyRuttv3tKCCwWV4uo5M1m0bC0v96WZ3JykY9Z0jWIaw8xshbu35Xut5NpK4Tf7+4fdUUTqZnJzsuLuoeZkYkDFV9VcamyljlaabWZ/MrO3zOwvZrbBzP4Sd+NEpDyVTmRLJpowY0gpcCWqG1epdw7fBU509z/G2RgRqT0jCAKF1ohQzaXGVGpC+lUFBpGRrbO7Z3s3UDmGy1Go5lJjKvXOocvMFgOdwObsRne/K5ZWiUjZFi1bG9kKcVmqudS4Sg0OuwMbgdwKqQ4oOIiMEFF3/6Q0WqmhlVpb6ey4GyIi1almpNJgPzhtJp+dqaDQyEodrTTBzM43s+vM7Mbsn7gbJyKlyzdrulIrX1wfyXlk9Co1If0fwHuAWcCvCGofVVOZVUQilm/W9FlHTiVVQUJ5yQoV4Wt0peYc3ufup5rZZ939J2b2n8Cv42yYiJSvvTWVN0cw47JfsGFz6cnqDZu20tndo3xDAyv1ziETPvaZ2SHAJODd8TRJRKLU2d1TVmDIUhnvxlbqncP1ZrYHcAlwD7ArcGlsrRKRyFx+75qKjktn+pl/zxrVWmpQpQaHh8I1HB4jXJXNzPYrfoiI1Ftndw/rN2aG37GAvnSGvnRwvGotNZZSu5XyraewJMqGiEj0oq6LpFpLjaPonYOZHQQcDEwys9k5L+0OTIizYSJSvTjqIqnWUmMYrltpOvBpoBk4MWf7BuDLcTVKRKJRzcQ4M8i33ItqLTWGosHB3X8G/MzMjnL339SoTSISkY5Z0wes0VCOfIFBtZYaR6k5h5PMbHczS5jZQ2bWa2ZnxdoyEana4IlxzckEiabKlgPNLkWqZHRjKHW00vHu/k0zOwl4HphNMHLp5rgaJiLRGDwx7u4VLzH3jlVln0fDWBtLqXcOifDxBOAOd38rpvaISMxO+tA+FR2nUUqNpdTgcK+ZPQ18CHjIzFqATfE1S0TiUums556+NEcvfFizphtEScHB3ecBHwHa3D0DvAN8Ns6GiUg8qrkDyE6EU4AY+4oGBzM7LnycDRwDfDb8+X8RBItix15jZq+amZvZfYNeMzN7dPBrZjbZzO43s01mtk5Jb5HoVTtPIZ3pZ+7ilUybt5Rp85bSesUDChZj0HB3Dh8LH08kmO8w+HE4txXY/mXgw3m2/ztwHPBPwDrgJ2b2vhLeR0RK1DwxMfxOw8gd5bp+Y4aOJasUIMaY4YLDBjO7CPhDzp81wOrw54Lc/QLgqsHbzey9wHcJivjlbt+TIOj80t2/D8wP2/f3pVyIiAyvs7uHtzdtjfy8mX5XwnqMGS447ArsRpCIPg94LzAZ+CpweIXv+W/AL4G7B22fBhiQ/frxUvi4f4XvIyKDLFq2lsy2PLPbIqCyGmPLcDOkLwcws8eAw919Q/h8PrC03Dczs08AnwI+Cewbbp5oZpPz7T7Muc4FzgWYOnVquU0RaUhxfoCrrMbYUupQ1r2BLTnPt4TbyjWFoGDfr4FHw23HAj8lmFznBEuQAmRn2zyb70Tufr27t7l7W0tLSwVNEWk8cX2AJ5pMZTXGmFJnSP8UeNLMsl1B7cBNxQ4wsxOAQ8KnU8zsHOBPwKnhthbgOmAFcLm7vxmOXJoV5jnagW3he4tIBPLVWjIGJpjLtcv4Jr59kspqjDUlBQd3/7aZ3Q98NNx0trt3D3NYB/Dx8OdDgRvC424CMLNp4Wv/4+7Z9ajPA24EvgO8Fu7/p1LaKCLDy36A567uVmnV1kSTcflnDuaMI/YdfmcZdczzlV4cZdra2ryrq6vezRAZlY5e+HBZAWJ80zim7JHkmdffofvST7LHLuNjbJ3EycxWuHtbvtdKzTmIyBjVMWs6yURTyfvvnmzimdffAWDeXU/F1SypMwUHkQbX3priXz57MLtN2Gl7We9xRcYKvv72jjWpf7W2V5PfxigFBxEBYMOmrTiwy847ccYRU0u6m9i0dRsXLl6pEhpjkIKDSIPr7O7h0p+t2f68py/NnSt6OHzqpJLPsX5jho47VEJjLFFwEGlwi5atHbKMaDrTz/Jn15d1nsw2Z/49a4bfUUYFBQeRBldo1nR/BSMZ+9KZ4XeSUUHBQaTBFZo13WSVrTUtY4OCg0iDyzeUNZlo4vQjppAoNmwpjz0iKAcuI0Op5TNEZIzKN2u6Y9Z02ltTtO27J9+4fSX9JfYwXXbiwTG2VGpJwUFEaG9NFayNVE6F7651bzL/njXbcw97TExw2YkHq+7SKKTgICJ5dXb3cPFdq8sqynfz8hcGPM+uEgcoQIwyyjmISF75hrhWQqvEjU4KDiKSV5QLA2mVuNFHwUFE8opyYSCtEjf6KDiISF7lVmstRKvEjU5KSItIXtkE8jduX1XRbGnYMVoJgnUjBg+VlZFLwUFECmpvTTF38cqKjm0y2x4Ycpcm7elLc/Fdq+la9yaPPN2rgDFCKTiISFGVLiXa787Fd61mQmJc3sJ+tyx/Yfsw2WzAAA15HSmUcxCRoqrJPaQz/azfmL8Y3+COqnSmX0NeRxAFBxEpqr01xYLZM2pSiE9DXkcOBQcRGVZ7a4p//dxhkYxeKkZDXkcO5RxEpCS5Bfp6+tI0mVU8iimfZKJJQ15HkFjvHMzsGjN71czczO4Lt+1pZj8Pt280s9+Y2YdyjjnazJ4ys81m9nszOzzONopI6dpbUzw+7zieX3gCzyz4FKmIvum/a5fxLJg9Q8noEaQW3Uq3DXq+OzAZWAj8H+AIYAmAmU0A7gR2A+YCewNLzCzee1kRqUi1OYKmMI3x/TkzFRhGmFi7ldz9AjObBlyQs/kl4HB33wZgZp8BDjezicAsgoDwTXe/zszeA1wKHAM8FGdbRaR8lQ5zzcquE7H37jtH1CKJSs0T0u6+NScw7AscBKxw943AfuFuPeHjS+Hj/rVtpYiU4tiDWqo6flIy+H763kkDu6c6u3s4euHD7DdvKUcvfJjO7p58h0uM6jZaKbwr+DmwGfj7QrsVOf5cM+sys67e3t44migiw3jk6cr/7yWajL9+314AbMtZUSi7jkRPXxpnxwQ5BYjaqktwMLPJwKPAe4Hj3X1N+NJz4eM+4WO2E/LZwedw9+vdvc3d21paqvv2IiKVqSrn4LDnLuMB+OP//GX75nzrSGiCXO3FmnMwsxOAQ8KnU8zsHOC3BEnn9wOLgPeZ2fuAe4H7gdeA88xsA/Al4HmCQCIiI0w1OYfMNufu7N1AzojYQgFHE+RqK+55Dh3Ax8OfDwVuAM4mCAzZ17P2c/fnzexU4FrgB8Aa4MvuXv1yVCISuY5Z0wcU1SvX25uD475+azdvvrOFyc1Jmicm8pbc0AS52op7tNIxBV66qcgxjwEz4miPiEQrirLeAG+8swUI8guJcUaiycj07zifJsjVnspniEhVsqU1EuOiqb2U2ebsMn4nJuy043wTEvqoqjX9jYtI1dpbU+w6IbqOiL50Bs8ZrLh+Y0YjlmpMwUFEItFXoDR3Jcxg89ZtA7ZpxFJtKTiISCSiTBgXSl9oxFLtKDiISCQ6Zk0vPGs1IpOSCc2crhEFBxGJRHtrasjqblHbsHnrgJnTHUtWKUDERMFBRCITVQnvQvq3DQw/mX7n8nvXFNhbqqHgICKRqUXX0mDrN2Z09xADBQcRiUx7a4ozj5waeYBINBU/o4a5Rk/BQUQidWX7DK6aM7Pq87TsGqzxsMv4JhadchjNyUTBfdOZfubfo+6lKCk4iEjk2ltT7LpzdZPiet/eDMCnD51Me2uK+Z85uOgs7L60upeiFHfhPRFpQJ3dPaS3bI3kXM/0bgB21HG6cPHKgvvOv2fN9v06u3tYtGwtL/elmdycpGPWdC1FWgYFBxGJ3KJla+mPaFzrqpfeorO7h/bWFO2tqaLBoS+dYeblD9CXHjhbO7tgEKAAUSIFBxGJXJQzmTP9vr1sRinlMwYHhqxs+Q0Fh9Io5yAikYt67YXshLdKFxbKUvmN0ik4iEjkOmZNJ5loivScmQj6qYoFrc7uHpXmyKHgICKRa29NsWD2DFLNSYxg5vRZR06NfQZ1McUWDOrs7uHiu1YPKM3R6HMnlHMQkVhkE8iDHXDxz6taNa5SC2bPKJhvuPzeNUOWOm30HIXuHESkpuoRGAC61r2Zd3tnd0/eNauhsXMUCg4iUlP16lq6efkLtF7xwJCuomIjoKJOrI8mCg4iUlNxJKtLlW+50WIjoHJzFI2WsI41OJjZNWb2qpm5md2Xs/0DZvaEmW02s7VmdnzOa0eb2VPha783s8PjbKOI1NbgZHWxmklxyF1utNgHfDIxbsBs60ZLWNciIX0bcMGgbbcCU4GLgPOAO8xsKrAZuBNIA3OBfwaWmNn73b0fERkTBierp81bWtP37+lL03rFAwVzDQATcu5uFi1b23AJ61iDg7tfYGbTyAkOZtYKHAZc5+7Xmlka+DFwCvAmsDfwTXe/zszeA1wKHAM8FGdbRaR+msxqnqguFhgGv14oMT14+1iq51SPnMN+4WP2fuyl8HH/YV4TkTGqXiOYhpPtNiqUmHbYnuS+pHM1cxevHDNdTyNhnkOxVTwKvmZm5wLnAkydOjXqNolIDaWak1WXxohDdo2IN9/ZXHCf9RszBYsB5uY3RtsdRT3uHJ4LH/cJH7N/Q88O89oA7n69u7e5e1tLS0ssDRWR2qjnCKZi+tIZLrp9JenMtorPkVsXKntHceHilVzSuTq6hsYg1jsHMzsBOCR8OsXMzgF+BTwFnGZmawgS0hsIEtGbgNeA88xsA/Al4Hng0TjbKSL11d6aYs3Lb/Gfv32BjVv6mdyc5NiDWrh5+Qv1bhrbquzxMstfFyp7bVe2z6juDWISd7dSB/Dx8OdDgRuAs4EzgB8B3wfWAZ9z9z4AMzsVuBb4AbAG+LJGKomMfT/9zTo2b93Gcws+hVnQo/yfv32h6g/neiuWTrl5+Qu07bvniOxiinu00jFFXj6qwDGPASMzlIpIbDZvDbpusoEBqv/WPhrkrl43kmiGtIiMSKN1lE+5Ci1OVG8KDiIyIpWy6hswIhPZ5cpX86neFBxEpO5yPxizdYtKqYiaak6yYPbo74XOV/NpsFrXdjIfoZNPytHW1uZdXV31boaIVCBbtyi3PEUy0cSExLhhZzE/v/AEgIKlMPaYGNRtGu48I0WqOcnj844DBs62npRM8M6WrQNGPSUTTUXXqCiFma1w97Z8r+nOQUTqqqpxGKcAAAlJSURBVFDdIvfiXUY5eWsuO/FgEk0D58wmmozLTjx41AQGCOZATJu3lGnzlnJhzmzrvnRmyHDYdKafCxevjO0uQsFBROqqUPfRW+kMC2bPIJnI/zF15hE7KiO0t6ZYdMphA5YlXXTKYSNyFFDU4irTMRLKZ4hIA5tcoHTG5Obk9uqtl3Su5tbfvki/O01mnH7ElCGTxwotS9qcTIzYEUFRiaNCrIKDiNRVx6zpeXMOuQvtXNk+o+KZxPM/czAdd6wiU2TSRNM4o3+UT6qIujaVupVEpK4GL/6THYEU1bfg9tYUi049LO/ypOMMzjpyKv9a4PXRJsp6TRqtJCKS45LO1dyy/AVG4ydjkxnPLPhUyfsXG62kbiURkRyDu7A6u3uYf8+agnkLs+L1k2opynUx1K0kIlJEe2uKlZcdz9VzZg4ZWptMNHHmEVNLnqU9MTFu+9yLODRZseVxyqM7BxGREmRzIPkW7Wnbd08WLVtLT18ag7xdUokm4zuzDwUYNkFeqdOPmBLZuZRzEBGJUHZmc09fevva2KlBq78N7qoaZ0EF2kKBpRRnHTm17BFdxXIOCg4iIiNMZ3dP3ruLQsEjt+xGOZSQFhEZRQp1YQHDzgmJioKDiMgIVGjGN+TPe0RNwUFEZBQpFjSipKGsIiIyhIKDiIgMoeAgIiJDKDiIiMgQCg4iIjKEgoOIiAyh4CAiIkOMifIZZtYLrKvw8L2A1yNszmiga24MuubGUM017+vuLfleGBPBoRpm1lWotshYpWtuDLrmxhDXNatbSUREhlBwEBGRIRQc4Pp6N6AOdM2NQdfcGGK55obPOYiIyFC6cxARkSEaIjiY2dFm9pSZbTaz35vZ4QX2+4qZvWRmaTP7mZm9q9ZtjUop12xmnwlf22Bmr5vZjWaWrEd7o1Dqv3O47wfMbJOZuZmdUst2RqmM3+1DzOzh8Hf7DTP7bq3bGpUSf7d3NrMfmVlveM3dZlb+UmkjgJldY2avhr+r9xXZr+Tf/1KM+eBgZhOAO4HdgLnA3sASM2satF8r8EPgj8BlwAnAVbVtbTRKvWbgMOC/gIuAFcDZwDdr2NTIlHHNmJkBNwD9g18bTcr43U4CvyD49/7f4Z93atvaaJTx7/x54EvASuBSgmu/oYZNjdptxV4s5/e/ZO4+pv8AJxEsu9oRPr8ifP6JQfv9INz+4fD5Y0AGmFDva4jxmsfn/Dwj3Of2erc/zmsOX/sH4EXg++E+p9S7/TH/O38x3H4OkKx3u2t0zV8Jt18FzATSwIp6t7+K654WXs991fy9lPNnzN85APuFjz3h40vh4/4l7LcTMCW+psWmpGt29y05T2eFj4/F2K44lXTNZpYCFgDnAX+pTdNiU+rv9gfDx4uAjWFXy+fiblxMSr3mnwB3AxcC3cBG4AtxN66OSv17KVkjBIfBLOL9RoOi12JmJwPfAX4O/HtNWhS/Qte8EOgCngb2DLe9x8x2rUmr4lXomncOH18BTgY2AzeZ2W41aVW8Cl3zkQRdw7cApwFNBNc8lv5fF1P1dTZCcHgufNwnfMwuvvqsmU0ws0SR/bYSdD+MNqVeM+E3yNuAR4CT3X209sOXes1TgOOAPwFfD7f9X6C9Jq2MVrm/27e7+13Ar4EkMLk2zYxUqdd8KjAe+KG7Lyb4QnA4QR2iMSFMumcDf8G/l4rfoN59aTXoq5sAvBr+5Z1HcNv1HHAAOX14wIfC5w8SJGW3Av9R7/bHfM0nhNfZS3DLfRpwXL3bH/M1fxw4Jfxze/ja94Cp9b6GGK95MrAJWA58GXiNsNu03tcQ4zV/I3x+D3A+QQL+dcK5XaPpT/j/9Fvh9awiyB29H3geeHuYv5emit+33hdeo7/cjwGrgS0E/Y9t5EnwECQqe8L/SPcCe9W77XFeMzA/fJ7759F6tz3uf+ec/bPXPyoT0uVcMzAbeIag7/0J4PB6tz3Oaw4/LH8UfmBuJBiNd2y9217h9T6a5//pF3KDQ6G/l2reVzOkRURkiEbIOYiISJkUHEREZAgFBxERGULBQUREhlBwEBEZJUotwjfomClhIdF3zOwtM7ullOMUHEQAM3sifJxmZmdEfO5/yvdeIhUqWoQvVzgj/G7gk8AigjlcvSUdq6GsIjuY2THAP7r7p8s4Zid331rk9bfdfSyU55ARwMymEUxwW5r9PTWzTwPfBt4H/Jngd/jBsEz5Q+FrVwKbvcQPfd05iBB8gIc/LgQ+amYrzWyumTWZ2SIz+11YK/8r4f7HmNmvzewegrLnmFmnma0wszVmdm64bSGQDM93S+57WWCRmf3BzFab2Zyccz9qZkvM7GkzuyVbE8jMFprZf4Vt+V4t/45kZDKzAwnKdaeBfyGonXW3mb2XHUUXTyaYDPgXM7uglPPuFENbRUazeeTcOYQf8m+5+4fDOjaPm9kD4b6HA4e4e7auzRfd/c1w/YTfmdmd7j7PzL7m7jPzvNdsgnLShxHU/PmdmWWr4rYCBwMvA48DR5vZHwlKMx/k7m5mzZFfvYxGnySoI3VE+CfrKHYUXcwQ/O78C3C1mf3C3f+72EkVHESKOx441HasFjeJoK7NFuDJnMAAcIGZnRT+PCXc740i5/5r4FYPih2+ama/Aj5MUEr8SXd/CcDMVhKUh1hOUNrlx2EysqSEpDSM7xLUhsv6Y87PS939Z2Z2JMHaLfsBCg4iVTDg6+6+bMDGIDfxzqDnfwMc5e4bzexRgvo+ldqc83M/QZG8rWb2V8AnCAoHfo2gwqw0CDM7ATgkfDrFzM4BfknwZWU2Qb6hGfgcQWXa+wkKLZ5sZn8m6F56m6D2UlHKOYgMtIFgqcWsZcB52VLQZnagme2S57hJwPowMBxEsJ5AVia3THqOXwNzwrxGC0HhtCcLNSxcc2KSu/+cYCnIw8q5MBkTOgjyYgCHEix9ehRBYHibYEXLuQRFFte7e5rgi8Rm4FqCvMNsd39tuDfSnYPIQE8B/Wa2CriJ4D/bNOD3YVK4l/xrP/wC+GqYF1hL0AWUdT3wlJn93t3PzNl+N8F/7FUElTa/6e7/EwaXfHYDfhauF2wEK7tJA3H3Y4q8vLTAMb8m6Eoqi4ayiojIEOpWEhGRIRQcRERkCAUHEREZQsFBRESGUHAQEZEhFBxERGQIBQcRERlCwUFERIb4/4/G10+SXG1lAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_learning(1000000, lengths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ant Colony Optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting scikit-opt\n",
      "  Downloading scikit_opt-0.5.9-py3-none-any.whl (27 kB)\n",
      "Requirement already satisfied: numpy in /Users/ben/anaconda3/lib/python3.6/site-packages (from scikit-opt) (1.18.5)\n",
      "Requirement already satisfied: scipy in /Users/ben/anaconda3/lib/python3.6/site-packages (from scikit-opt) (1.5.2)\n",
      "Installing collected packages: scikit-opt\n",
      "Successfully installed scikit-opt-0.5.9\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "source": [
    "!pip install scikit-opt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy import spatial\n",
    "\n",
    "distance_matrix = spatial.distance.cdist(cities, cities, metric='euclidean')\n",
    "num_points = cities.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sko.ACA import ACA_TSP\n",
    "\n",
    "N = len(distance_matrix)\n",
    "def cal_total_distance(tour):\n",
    "    '''The objective function. input tour, return total distance.\n",
    "    cal_total_distance(np.arange(num_points))\n",
    "    '''\n",
    "    return sum([\n",
    "        distance_matrix[tour[i % N], tour[(i + 1) % N]]\n",
    "        for i in range(N)\n",
    "    ])\n",
    "\n",
    "aca = ACA_TSP(func=cal_total_distance, n_dim=N,\n",
    "              size_pop=num_points, max_iter=200,\n",
    "              distance_matrix=distance_matrix)\n",
    "\n",
    "best_x, dist = aca.run()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x7fc8e6368e10>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO2dd3wVZfb/3+deSkARlKD0BDH5ir2grrK6VlxXXburxoKiqNhWd5d1xYIi9rWhWBa7EfeLZdWvZX+uKyLqglixrI1mUJEmLZCE5Pn9ceaaENJn7szce8/79cpr7p32nEwmnzlznvOcR5xzGIZhGLlBImoDDMMwjPAw0TcMw8ghTPQNwzByCBN9wzCMHMJE3zAMI4doF7UBdcnPz3eFhYVRm2FkKe+9995i51yPKNq2e9tIJ625t2Ml+oWFhcycOTNqM4wsRUTmRdW23dtGOmnNvW3hHcMwjByiWdEXkTtFZKGIOBH5vzrrB4nI2yJSISJfiMjQOtuGiMjH3rb3RWSXdP0ChmEYRstpqaf/ZAPrJgFbA5cAVcBkEekqInnA00AX4GJgC+ApEUkGYK9hBIqI5HlOixORu7x15tAYWUuzMX3n3IUiUghcmFonIjsDOwITnHN3i8ga4AHgWGApKvSjnHMTRKQncAWwL/Ba0L+AYfjkSqBvvXWTgP6oQ3Mu6tD0BypQh2YN6tCMRh2aIudcdXgmG0FTVVVFWVkZa9eujdqUJsnLy6Nv3760b9++zedoa0fuAG+5wFuWecstga5NbNtA9EVkBDACoH///m00xzBaj4jsgIr3FcDN3jpzaHKQsrIyunTpQmFhISIStTkN4pxjyZIllJWVMWDAgOYPaISgOnKbukpNXkHn3P3OucHOucE9ekSSTWcAlJZCYSEkErosLY3aorQiIglgInA3UDetpimHpqltDbUxQkRmisjMRYsWBWK3kR7Wrl1L9+7dYyv4ACJC9+7dfb+NtFX053jL1GtxH285u5ltRhwpLYURI2DePHBOlyNGZLvwnw4UAo9Se492Beq/N5tDkyPEWfBTBGFjs+EdETkU2M772k9EzgTeAD4GThCRT9G450o03rkW+BE4V0RWAsOBucAU39Ya6WH0aCgvX39debmuLymJxqb00w/oAXxUZ93JQG/vc0NOy9ImtrWaZasreeitOfx6u15s03uTtpzCMFpNSzz9PwE3eJ93AP4GDAFOAr4AbgU6AMc7535yzq0FjgNWAXegD4DjrKMrxsyf37r12cH/ovfpccAYb90rwChqHZrz0M7clEPzMrUOzbn4dGhWrK3izn9/zX9/WNHmX8LIHt566y122GEHOnbsyC677ML777+flnaaFX3n3L7OOan387Bz7lPn3J7OuY7OuWLn3Ct1jpnqnNveOdfBObezc86GIsaZ7t0bXp/FHevOuc+cc085555C31wBvnHOvUdIDk3Ce1WvsXmMcp61a9dyzDHHsHLlSm677TYWLlzIscceS3V18L5yrMowGBFwxx2weLF24NbU1K7v3BnGjYvOrhBxzk2hTnzeOfcpsGcj+04Ftg+i3VR4tsZmr8t5Xn75ZRYuXMhNN93EyJEj+eGHHxg7dixTpkzhgAMOCLQtE/1cpaYG/vhHuO02OOooOPxwuPJKKCuDTTeF8eOzOZ4fC1Kevk1ZGi+ufuFTPvsu2JDbNr034arDt210+5w5mv/Sp492E/Xtq91Gs2fPNtE3AmDtWjj1VJg8GS68EG69FZJJGDYMNtpIlyb4acfCO0ZjpNMRMNHPNZYuhSOOgGnT4K9/hYsvro0ziEBBgaZsGmkn4V32alP9WNGUR54uUoOtysp06MeCBToUZMstGxwC4gsT/Vxizhw45BBd/v3vcPzxG+5joh8aiYSFdwzlkEMOYfPNN+eee+6hS5cuPPDAAxQWFrLvvvsG3paVVs4VZs6EPfeEH3+Ef/2rYcEHE/0QsfCOkSIvL4/Jkyez8cYbc9FFF7H55pszefJkksng61Sap58LvPSSinx+Prz+Ogwa1Pi+BQWazbN6tcb3jbSRsOwdow777LMPs2bNSns75ulnO3/7G/z2t/A//wPvvNO04IOKPmT7wKxYIObpGxFgop+tOAdXXKE1dA46CN54A3r1av64lOhbiCftpDx9i+kbYWLhnWykshLOOgsefRSGD4d77oGW1t820Q+NVEzfsnfigXMu9kXXgnAQzNPPNpYvh0MPVcG/5hoN77RmwoXevaFdOxP9ELCO3PiQl5fHkiVLYv3Wlaqnn5eX5+s85ulnEwsWwG9+A599Bg89pIOsWksyCX37muiHQMJzuawjN3r69u1LWVkZcZ/3IDVzlh9M9LOFWbNU8JcvhxdfhKFDmz+mMSxtMxSsDEN8aN++va/ZqDIJC+9kA//+N/zyl1BdDVOn+hN8MNEPCQvvGFFgop/plJbCr38N/frBf/4DO+3k/5wFBfDdd1BV5f9cRqNYnr4RBSb6mYpzcP31cPLJMGSI1tIJqv59QYFW4Swra35fo838nKdvrr4RIib6mci6dTByJFx2GZx0ErzyCnTrFtz5LW0zNBJi4R0jXEz0M43Vq7X+/b33wqWXwmOPQceOwbZhoh8ayYRYeMcIFcveySQWLtTJTt57D+6+W739dNCvny5N9NOOiJinb4SKiX6m8OWX2mH7ww/w7LNaTydd5OVBz54m+iGQEEvZNMLFRD8TePttFflEQqtk7rFH+tssKIC5c9PfTo6TEAvvGOFiMf248+yzcMABOm/tO++EI/hgufohkRChuqb5/QwjKEz048ydd8Ixx2ju/dtvw8CB4bVdUADffqupm0baELE8fSNcslP0S0uhsFDDIYWF+j2TqKmBP/wBLrpI57N97TXo0SNcGwoKtFrnDz+E226OkRCxmL4RKtkn+qWlWkN+3jwdwDRvnn7PFOFfuxZOOAFuvRXOPx+eego6dw7fDkvbDAVN2YzaCiOXyD7R/8tfoLx8/XXl5TB6dDT2tIalS3XCk8mT4eabNbyThjkyW0RhoS5N9NNKwsI7RshkT/bO6tUwfrzGoRsi7tP/zZ0LhxwCs2fDk0/C734XrT3m6YeC5ekbYZP5ol9RAffdB9ddp4OXOnWCNWs23C+oujTp4L33dOKTigp49VXYZ5+oLYIuXTRjyEQ/rSTEau8Y4ZK54Z1162DiRCgq0g7PQYPgrbd0pqj6MfC8PBg3Lho7m+Pll+FXv9JSCm+9FQ/BT2Fpm2nH8vSNsIm/6NfPxHn8cZg0SUX+rLN0su9XX9Wa8nvtBSUlcP/9Klgi+rPbbro+bkycqGUViou1LPI220Rt0fqY6KedhIV3jJCJt+g3lIlz6qlaWbJTJ3juORXLAw9UcU9RUqIx8poaOOccmDED4jQNmnNw5ZX60DroIHjjDX14xY2U6JsnmjYSCSvDYIRLvEV/9OgNM3Gcg/x8+PBDLU3Q3Oz155+vsfKJE9NnZ2uorITTT4exY+GMM+D55zV+HkcKCmDVKli2LGpLshYL7xhhE2/RbyzjZsmS2lmlm2ObbbSMwYQJ2g8QJStWaIftI4/AmDH6IGrfPlqbmsIyeNKOhXeMsIm36DeWcdPaTJwLL9RZoP7xD/82tZUFC2DvvWHKFHjwQbjqqubfUqLGRD/tWBkGI2ziLfrjxm2YidO5c+szcQ49VDuB77wzMNNaxSefwC9+oTn4L76o4Z1MwEQ/7Vh4xwibeIt+KhMnVXemZ0/93tpMnGRSY/tvvgkffRS8nU3x+uvwy19CdbW2P3RouO37IT9fO8xN9NOG5ulHbYWRS/gWfRH5vYjMFZEKEZkjIhd464eIyMfe+vdFZJc2NVBSAlOn6uebbmp76uUZZ+hbwvjxbTu+LTzxBBx8MPTpo1lGO+0UXttBIGJpm2nGPH0jbHyJvogUAbcBNcAlQHvgThHpBzwNdAEuBrYAnhKRthWS2XJL7bj96qu2G7vppnDKKZoGumRJ28/TEpyDG27QB9Ree8G0afEeEdwUWS76IjJdRFaKSLmIzBSRfbz1l4lImYisFpG/i8gmdY4529u2RkSeE5HubW3fOnKNsPHr6aeOXwD8C/gBqAB+gQr9BOfcBOABYACwb5ta6dBBY/JffunP2vPP1yqW6UzfXLcOzjtPC7+dcAL885/6wMlUslz0gbeBC4GxwE7ARBE5BhgHvAtcBxzvfUdEdgbuBT4HrgIORR2fNmF5+kbY+BJ959wXwKXAEOC/wM7ACMCbWZsF3rLMW25Z/xwiMsLzsGYuamoAVVGRP08fYLvtYL/9dFLxdKRvrl4NRx8N99wDo0bpW0XHjsG3EyYFBbB4sf5u2cklwAvAa6jDUgP8ytt2i3NuHOrMnOatG+YtL3PO3YQ+NE4Ukby2NG7hHSNs/IZ3egAXAB8CRwIfAXcBG9fftbFzOOfud84Nds4N7tHURCHFxerp+/0HufBCrcT5/PP+zlOfH3/UB8qLL8Jdd8GNN7Z8LEGcSWXwxL1KadvpCiwCpgOVwJned4B9RWQ3IB/o4oVxBnjb6jo07ah1dH6mJQ6NiFBtmm+EiF9V2hfoAzzjnHsOeAaN43/ube/rLft4y9ltbqmoSEeHLlzY5lMAWuumoCDYDt2vvoI999TUzGee0fBOtpD9aZurgKFoiCcPuAa4B31zvRaYAaz19l3bwPG+HJqEWHjHCBe/oj/HW54sIsOBVGrNl8CPwLkici4wHJgLTGlzS8XF3pl9xvWTSRXlKVPg44/9nQt0svI999TRtq+/rtMbZhNZLvrOuXXOuVedc+NRgd/P27QjsBtQDHwHzHfOrab2nq/r0KwDGpnIoWksvGOEjd+Y/kzgD0BH4G5veb5z7iPgONSLugN9ABznnKtuc2NFRbr0G9cHGD5cyx8MGeJvHt1nn4X994du3VT899jDv21xo3dvaNcuK0VfRA4WkQdEZLiIjAH2Ahai9/HVwHZoB28xcIt32KPecpyIjPKOedI519BbQLMkRSxP3wgV35OoOOduBW5tYP1UYHu/5/+ZggIVar+ePmgN+5oaDRdB7Ty60PJxAOPHax3/3XeHF14If+LysEgmoW/frBR9YCmwB3AS2ok7DRgFVKN9VFsCS9AHwF0Azrn3ROQ8YDSwN/AympbcJqwMgxE2mTNzVjIJAwcG4+mPHq0jZOtSXg6XXtqw6JeW6jHz50O/fpoF9NJLGsp54oloJi4PkyxN23TOvYt68w0xqInjJgATgrAhIUK1JeobIZI5og+1GTx+aSwTpaxMwxk77wy77KI/8+fDZZfVlnieP19/DjoInn46uonLw6SgQCepMQInkYBKS98xQiSzRL+oSAc71dT4S4fs379hz3XTTVXM338fXnml6aIoX3yRG4IP2ufx3XdQVRXvUtAZiHXkGmGTWYnkxcU6Icq3bUqUqKWx6p3jx2ut+1mzYOVKrZfTGH5tyCQKCvQBWFbW/L5GqxArw2CETGaJflAZPPXn0S0o2LB6Z+fOmo2TSlmsT6bW0mkLWZ62GSVJy9M3QiazRD+oXH1Yfx7duXMbz9oJqqZ/JpMS/blzIzUjG7HwjhE2mSX6vXur4AaRwdNSWvJWkO308yoMmKcfOGJ5+kbIZFZHroiGeILw9FtDSUluiXx9OnaEXr1M9NNAwvL0jZDJLE8fgqm2abSeLM3VjxoL7xhhk3miX1ysc81WVUVtSW5hop8WEgkse8cIlcwT/aIiHU1rnYrhUlCgaaoWgA4UMU/fCJnME/0gM3iMllNQAJWV8MMPUVuSVSRFfE8RYRitIfNEP8hqm0bLsVz9tGAduUbYZJ7o5+drKWPz9MPFRD8tWME1I2wyT/RTaZvm6YeLiX5aEAvvGCGTeaIPwVXbNFpOly5akM5EP1AsvGOETWaKflGRZpKsWRO1JbmFpW0GjuXpG2GTmaJfXAzOwTffRG1JbmGiHziJhFXZNMIlM0XfMniiISX65pkGRsKqbBohk9mib3H9cCko0HmFly2L2pKswbJ3jLDJTNHv2hU239w8/bCxDJ7A0Y7cqK0wconMFH2wDJ4oMNEPHCvDYIRN5oq+5eqHj4l+4CQsT98ImcwV/eJirQOzYkXUluQO+fnQqZOJfoAkE5anb4RL5op+qjP366+jtSOXSM0cZqIfGJanb4RN5oq+VduMhsJCE/0AsekSjbDJXNEfOFCXFtcPF/P0A8XKMBhhk7mi37mzTthtnn64FBTA4sWwenXUlmQFFt4xwiZzRR8sgycKUhk88+dHa0eWYHn6Rthktuhbrn74WNpmoIgIYKUYjPDIbNEvKtKSAEuWRG1J7mCiHyjJhIq+eftGWGS26FsGT/j06gXt2pnoB4Sn+VZ/xwiNzBZ9q7YZPsmkdqCb6AdCKrxjnblGWGS26A8YoCJknn64WNpmYCR+julHbIiRM2S26HfooIOFzNMPj9JSePddeOstvfalpVFblNGkwjsfzF9GVbWN0jLST2aLPlgGT5iUlsKIEbU5+vPm6XcT/jbTJa89ACdNnM5T75VFbI2RC/gWfRHpJiKPishPIrJKRKZ664eIyMciUiEi74vILv7NbYBUrr69H6ef0aOhvHz9deXlut5oE8fu2pdHztgdgBVrqiK2xsgFgvD0HwRKgAeA3wNfi0ge8DTQBbgY2AJ4SkSSAbS3PsXF6nl+/33gpzbq0diArAweqCUi00VkpYiUi8hMEdlHlOtF5DsRWSsi/xWR39U55kgR+drbNkVEBrS1/Q7tEuwxYDPA0jaNcPAl+iKyJXAUMAn4C/CQc+4M4BBU6Cc45yagD4QBwL6+rG0Iy+BJP6tXw/XXa5XNhujfP1x7guVt4EJgLLATMBE4ELgU+B74E9AHeFhE2otIT+BJYIW3bVfgET8GpC6rZfAYYeDX09/GW+4GrAZWi8iNqMADLPCWqWDllj7b2xDL1Q+W0lLtoE0kNEvn1FO1uN1ll8EOO0Be3vr7d+4M48ZFYmpAXAK8ALwGVAA11P5ffAO8CiwHVnrbTgQ6Atc758YDzwJ7i8jAthqQ9FTfcvWNMPAr+h295UbA74C3gFFAu3r7NeIigoiM8F6rZy5atKj1FvTrp1k85un7J9VRO2+e9pHMnw+PPQabbabZOh98ABMn6sMgVVv//vuhpCRqy/3QFVgETAcqgTOB/wfcDRwHfA50B05yzlXTCoempfd2alSuib4RBn5Ff463fNM59wzwv973lMj39ZZ9vOXs+idwzt3vnBvsnBvco0eP1luQTMJWW5mnHwQNddSChnf22ks/l5TA3LlQU6PLzBZ8gFXAUDTEkwdcA/wPcDIq/kcDC9HwzkYNHN+oQ9PSe1tEELH6O0Y4+BX9D4BZwAEichZwOlANvAj8CJwrIucCw4G5wBSf7TWMVdsMhsY6ZL/9Nlw7QsQ5t84596oXqpkB7Accjr4BPOacexb4F+q4bEOto9OsQ9MaEiJUm+gbIeBL9J26Jieisc/xwGbAqc65T9BX41XAHegD4Djv9Th4iot12sTq9Jw+Z2isQzYTOmpHjtSaQCK6HDmy2UNE5GAReUBEhovIGGAv1KtPCfi5njNzGBr6mYN24lYCfxaRC9BEhmnOuW/8mJ8UwcZmGWHgO2XTOfepc25P51yec67YOfeEt36qc25751wH59zOzrmZ/s1thOJiqKzMao80FMaN047ZumRCR+3IkXDPPbUP/epq/d688C8F9gDuQtONp6Fe/jPATUAh6swsBU52zi12zn2POjrdgFvQt91hfn+FhE2QboRE5o/Ihdq0TYvr+6OkRDtmUxk6mdJRe//9rVvv4Zx71zm3nXOuk3Oum3NuP2+dc8792TnXx3NmtnHOTa5z3DPOuYHOuY7OuX38evngzaBlHblGCNTPsslMUmmbX30FQ4dGa0umU1ICL70E//kPfONby8KhsbBeBoX7khbTN0IiOzz9nj1h443N0w+KHj10HtxMYHYT/afJ4AeAp4tEwjx9IxyyQ/RFLIMnSPLzYcUKqKiI2pLGqaqCG26AbbdtXNxHjAjXJh8kE+bpG+GQHaIPKvrm6QdDKqc8rtNQvv027LIL/OUvcMghOl7gtNNqtyeTcO65MGFCZCa2Fpsg3QiL7BH94mL956+sjNqSzCc/X5dtGSGdTpYtg3POgSFDYPlyeO45eOYZ6NsXjjpK95k2DdatyyjBB+vINcIje0S/qEg77ubMaX5fo2lSnn5c4vrOwaRJMGgQ/O1vcMkl8Nln8Nvf1u4zfbp6+Lukp4J3ukkmxMowGKGQPaJfN4PH8EecPP1vvoFf/xpOOkkHic2cCX/9q3bc12XGDC0I16lTNHb6xEbkGmGRPaJvufrBEQdPv7ISrrsOttsO3nkHxo/X5c47b7hvTY1O4bjHHuHbGRCJhM0DZIRDduTpA3TvrtUgzdP3z2abaUZUVJ7+tGlw9tkawjn2WLj9dujTp/H9//tfzTbKYNHXMgym+kb6yR5PHyyDJyiSSRX+sD39pUs1zXLvvWHVKnjhBZg8uWnBBw3tAOy+e/ptTBMJS9k0QiK7RL+42Dz9oMjPD8/Tdw6eeEI7ah98EP74R/XyDzusZcdPnw6bbAJbb51eO9NI0rJ3jJDILtEvKtKiaw3VhDdaTmmppr9OnqyzaJWWpq+tr7/W0hklJdrWzJlw882wUUOl6xth+nTYbTcNjGcoCREruGaEQub+lzREKoMnU2rGxJHU7Fmp0bjz5un3oIW/shKuvVY7amfMgLvv1kFXO+3UuvOsWQMff5zRoR3wwjtWWtkIgewSfcvg8U9Ds2eVl+v6oHjzTRX3K66AI46Azz/XMshtqZXz/vs6PiODO3EBklZa2QiJ7BR9i+u3ncZmz2psfWtYuhTOPBP22UcfJC++CH//O/Tu3fZzTp+uy0wXfQvvGCGRXaLfpYtW3DRPv+2kY/Ys53SC9a23hocfhlGj4NNP4Te/afs5U0yfrrb17On/XBEilrJphER2iT5YBo9fgp4968sv4cAD4dRTYeBADcfceGPrOmqbYsaMjI/ng5ZhME/fCIPsE33L1fdHavasXr30e35+22bPqqiAsWO1NMJ77+n0hW+9pd+D4scfNcsow0M7YIOzjPDIPtEvLlYxWL48aksyl5IS+PBD/Xzlla0X/DfegB131GOPPFI7as85J/iUyiyJ50NqjtyorTBygewTfevMDYb8fOjQARYsaPkxS5bAGWfAvvtqSubLL8OTT9a+NQTNjBkZXVmzLlZa2QiL7BN9q7YZDImEZtWUlTW/r3PwyCPaUfvYY3DppfDJJ1odM51Mn655/kH1D0SIzZxlhEX2if7AgVoszOL6/unTp3lP/4svYP/9YdgwfeB+8AFcf/2GncFBU1Ojnn4WhHbAPH0jPLJP9PPyNIXPPH3/9O3buOhXVMDVV2vH7Icfwn336aCr7bYLx7avvtJ+myzI3IFU9k7UVhi5QPaJPlgGT1D06aPhnfphhylTVOzHjIFjjtGO2hEjwq19k0WduKBz5Fr2jhEG2Sn6qVx9i5H6o08frW3z00/6ffFiDePst5/OQ/vPf2p1zCgGRk2frrNnDRoUfttpwAquGWGRPZOo1KWoSIVq8eLaWaCM1pOabzg1Qc3atRrWuewyuPzyaKcmnDFDK2u2pV5PDLE5co2wyF5PHyyu74fSUp2EHPSNackS9fqvvVZH50Yp+GvXwkcfZU08H7TKpnn6Rhhkp+hbtU3/jB5dW145RU2NjqyNmg8+gKqqrInnQyq8E7UVRi6QnaJfWAjt2pmn74d0Vtv0S5Z14gIkrSPXCInsFP327WHAAPP0/ZCOaptBMWOGdjL7KckcMxIW0zdCIjtFH6zapl+CrrYZJNOnZ5WXD1pwzVlM3wiB7BX9oiJL2/RDqtpmQYGOcC4oaFu1zaBZtAhmz8460U+IlWEwwiE7UzZBPf3ycvjuOw0FGK2npCR6ka/Pu+/qMosyd8DmyDXCI7s9fbC4frYxfbqO/B08OGpLAsXmyDXCIntF33L1s5Pp02HbbXU0bhZhc+QaYZG9ot+3rxZfM08/e3Auqypr1sXmyDXCIhDRF5E8EflCRJyI3OWtGyQib4tIhbdtaBBttZhEArbayjz9bOLrr2HZskDj+SIyXURWiki5iMwUkX1EZIx3L6/3U+eYs0WkTETWiMhzItLdrx3JhJVWNsIhKE//SqBvvXWTgK2BS4AqYLKIdA2ovZZh1Tazi/QMynobuBAYC+wETASeAk70fs739vsAQER2Bu4FPgeuAg4FbvNrhE2iYoSFb9EXkR2Ai9F/gNS6nYEdgUnOubuBW4FNgGP9ttcqiovhm2+gujrUZo00UFoKI0fq58MP1+/BcAnwAvAaUAHUOOc+cc496Zx7EkgVGbrXWw7zlpc5525CHxonikieHyOsDIMRFr5EX0QSqGd0NzCzzqYB3jI1A0dqzr0tGzjHCO+1euaiRYv8mLMhRUVao2XevGDPa4RLaanW61+5Ur/Pn6/fgxH+rsAiYDpQCZyZ2iAiAowAVgCpxhq6t9sB/eqfuDX3dkKw8I4RCn49/dOBQuBRIJUM3xVoX28/aewEzrn7nXODnXODewRdBjmVwWMhnsxm9Ggdc1GX8nJd759VwFA0xJMHXFNn235AEfC4c251I8cHcm9beMcIC7+i3w/oAXwEPO6tOxn1jqA2zp96IMz22V7rSOXqW2duZpPG4m/OuXXOuVedc+OBGcB+IpLvbT7HW9YtLepNMrDevb0O+NaPHQkRnMNKMRhpx++I3P8FPvE+bwuMAV4BLgceBE4QkU+Bc4GVwNM+22sdW2wBXbqYp5/p9OwJ33+/4Xqfxd9E5GDgeDQu3w/YC1gILBGRLYAjgbecc5/UOexR9K1gnIi86h0zyTm31o8tyYS+MNQ4rbhpGOnCl+g75z4DPgMQkcXe6m+cc++JyElovP9WYB5wvHPuJz/ttRqR2ho8RmZSUaFlsusTTPG3pcAewEloJ+40YJRzzonI6WiY8t66B3j39nnAaGBv4GU0kcEXnuZTXeN+fgAYRjoIrPaOc24KdeKbzrlPgT2DOn+bKS6uTfUzMo+rroJvv4U//AGeekpDOv37q+D7rAvknHsX2OBbc+EAABOOSURBVK6RbTcANzSybQIwwVfj9Uj87OlbeMdIL9k7IjdFUZFm79SfBcqIP2++CTfdBGeeCbfcAnPn6uxdc+fGrxCcT5Kiom+jco10k/2iX1ysQjE73D5kwycrV8Jpp+lkOLfeGrU1aSdpnr4REtkv+pbBk5lcfLG+oT36qHbGZzniefo1Vl7ZSDO5I/qWwZM5PP88PPAAjBoFQ4ZEbU0opDJ2LFffSDfZL/qbbQbdu5unnyn8+KPG8HfcEa6+OmprQiMV3rGYvpFusnfmrLoUF5unnwk4p+UVli+Hf/8bOnSI2qLQSGXv2OAsI91kv6cPlqufKTz8MDz3HFx3HWzXYCZl1pJIZe+Y6BtpJjdEv7gYFiyA1Y2VT4kZpaVQWKhzAhQWBllRMr7MnQsXXQS/+pV24uYYlrJphEVuhHdSnblff62x4jiTqiiZKjA2b55+h6zLTf+Z6mo49VT9/Mgj+rDLMVLhnec/+o7uG8UzrJUQYei2PenaqX49RSOTyA3Rr1ttM+6i31RFyWwV/Vtv1YFYDz0EBQVRWxMJW2zSEYCbXvkiYkuaZtGqCkbuu1XUZhg+yA3R38q7STMhrp/GipKx5OOP4fLL4cgjdTBWjrJ3UQ9mXn4glevim6h/6J1vUrZsTdRmGD7JDdHfeGPo3TszMnj692940hefFSVjSUUFnHIKdOsG99+vBfJymPyNO0ZtQpP07taJH5b7KiZqxIDcCZ5mSgbPqFEbrkskYOzY8G1JN1ddpZ7+Aw9A0BPoGIHTq2se3/1knn6mkzuinym5+l98oR5v7966zM/XsfkLFjR/bCYxbVptMbXDDovaGqMF9Oyaxw8rzNPPdHJH9IuKYPFiWLYsaksaZ948uPdeGD5cRb6mRkeoHnusesWffNL8OTKBlSs1W6ewMCeKqWULvbp24qfyKlasrYraFMMHuSP6qQyeOId4rvGmZ73yytp1IjBhAnTtqh2dVVnwD5cqpvbYYzlRTC1b6LtpJwB+d99/IrbE8EPuiH7cq21+8YWOSB05Evr1W39bjx5w333w/vtw/fWRmBcYOVhMLVs4eNuedMlrx5JVNjdFJpM7oj9woHrNcY3rX3GFTgF42WUNbz/qKDjpJO3Q/eCDcG0LikWL4Kyzcq6YWraQ1z7Jcbv2o7yyOmpTDB/kjuh37KgDf+Lo6b//PkyerGGPprJYxo/X7aedBpWV4dkXBKliaj/9BI8/nlPF1LKJjTsmWV25zgrDZTC5I/oQ3wyeyy+HTTfVeWCbYrPNNJ991qza+H+m8PDD8I9/6Ny2OVZMLZvYqGM7nMO8/Qwmt0Q/lasfJy/lzTfh5Zfh0ku1s7Y5DjsMhg2DG26Ad99Nu3mBkOPF1LKJjTrqeM7VlesitsRoK7kl+sXFsGKFpkHGAec0ht+rF5x/fsuPu/12Pea002BtzPOmq6tryys88ggkk9HaY/hio47691tdYZ5+ppJboh+3DJ5XXtFBSqlO3JbStatmwHz++frpnXHktttg6lS4886cLaaWTWzUwfP0K8zTz1RyS/TrVtuMmpoarZw5YIAOxmotQ4fC2WfDLbfA228Hb18QzJqlv2OOF1PLJjb2wjurTPQzltwS/YICaNcuHp7+009r6uXVV7c9k+Xmm/V3GjZsw3LMUVNRASefbMXUsoyfY/om+hlLbol+u3aarx+1p79unYZ0tt1Wc+/bSpcu8OCD+hBrLL8/KlLF1CZOtGJqWURtR67F9DOV3BJ9iEe1zUcf1RG4117rv2Nzv/3gggvgjjvgjTeCsc8vdYupHX541NYYAVLbkWuefqaSe6JfXKyiXxPRZBUVFTBmDOy2GxxxRDDnvP56nSjm9NNh1apgztlWrJhaVmPhncwnNyZRqUtRkaY5LliwYY2bMLjvPvj2Ww3LBBXn3mgjHfy0997wpz/BPfcEc962cMklmpc/daoVU8tCUtk785aU8/n3K1p8XPeNOrD5JnnpMstoBbkn+nUzeMIW/VWrNKSz//5w4IHBnnvIEBXcv/4Vjj4aDjoo2PO3hOef1xj+n/8Mv/xl+O0baSeZELp1bs9j/5nHY/9pYIa3RujYLsFHVw0lr72N04ia3BP9urn6BxwQbtt33KFFx8aNS8/5x46FF1/UFNBZs1o2wjcorJhazjDprF8wb8nqFu//xpeLmDTjW1ZXrDPRjwG5J/p9+kCnTuFn8CxdqimWv/0t/OIX6WmjUycN8+y1l3r9DzyQnnbqU7eY2muvaXE7I2sZ1GsTBvXapMX7LyuvYtKMb6mqjlH5kxwm9zpyEwnt9Aw7g+emm7QExLXXpredPfbQ8MqDD6rXHwaPPGLF1IxGaZ9Umamqjih5wliP3BN9CL/a5vffaxmCk06C7bdPf3tXXaXie9ZZ6Z8ecu5cuPBC2GcfK6ZmNEj7pCYsVJrox4LcFP2iIpg9WwdJhcG4cTrN4Zgx4bTXsaN634sWqSCnCyumZrSADubpx4rcFP3iYhX8uXPT39acOVqGYPhwDSuFxS67aN2bxx/X0Es6qFtMrbAwPW0YGc/P4Z11FtOPA75EX0SKROR1EVkiIitF5FURGehtO1JEvhaRtSIyRUQGBGNyAIRZbXPMGPWAr7gi/W3VZ/Ro2GknLcy2eHGw586SYmoiMt27d8tFZKaI7OOt7yciz4nIahFZLiKldY6J770dQ9q380Q/qgGRxnr49fT7eOe4CngIOBCYKCI9gSeBFcCfgF2BR3y2FRxhVdv89FN47DGtld+nT3rbaoj27bXkw7JlcN55wZ23ogJOOSVbiqm9DVwIjAV2Qu9fAZ4FDgJuBkYBiwBif2/HkPYJvT+q1pnoxwG/KZtvO+d+lfoiIiXAtsCJQEfgeufcZBHZDThFRAY6577x2aZ/evSATTZJv6d/5ZWw8caaTRMV22+vbxujR8Mxx8Dxx/s/55gx8NFHOhgr84upXQJ0B7YELgdqgP1QMR8H3ABUuNpJYeN9b8eQnz19S9mMBb48fefcz7Nzi8hgYDNgKpB63V3gLcu85Zb1zyEiI7zX6pmLFi3yY07LEUl/Bs+778Izz+i8t/n56WunJYwaBbvvDiNHwsKF/s41bRrceKP2UWRHMbWuqBc/HagEzgS28bYdA5QDK0Qk1SMe73s7hljKZrwIpCNXRLYGngfmAhc0tEtjxzrn7nfODXbODe4RpteY7mqbo0er2F9ySfraaCnt2umgrVWrNL7f1jmC6xZTu+22IC2MklXAUDTEkwdcg3ryAFXAUcAc4HYRKW7g+Pjd2zHDUjbjhW/RF5FtgCmol7S/c+579J8EoK+3TAW0Z/ttLzCKi2HevPTMMfv66/Dqq/CXv8Sn6NigQTow7LnnoLS0+f0bIlVM7dFH4/N7+cQ5t84596pzbjwwAw3tfOttftE59xzwIiruA8iEeztmWMpmvPCbvdMPeB3IB+4F9hCRE9COrkrgzyJyAeotTYtVzLOoSD3e2QH/rzqnXn6fPnDuucGe2y8XX6yF2S64QKuMtoYXXtBiaqNGZU0xNRE5WEQeEJHhIjIG2AtYCLwA/AgcIyLD0TDPKuADMuHejhkW3okXfj39gcDmQBK4HpgETPK8/ROBbsAt6D/LMJ9tBUu6MnhefBHeeUc7cTt1Cvbcfkkm4aGHNPvmrLNaHuZZtEgnRNlhh2wrprYU2AO4C/g9MA043Dm3BjgWqADuRuP6RzvnfsyIeztmtEumsnesIzcO+Mrecc5NoZGYpnPuGeAZP+dPK+nI1U9Ndp6a0CSOFBXBDTfARRfpA+CMM5rev24xtX/9K6uKqTnn3gUaLBbknHsTaLBmRuzv7Zjxc3jH8vRjQW6OyAXNMe/RI1hP/+9/13lhr7lGc+Tjyvnnw777wu9/D/PnN71v3WJqYdQNMrKO2hG5JvpxIHdFH4LN4Kmq0pDO9tvD734XzDnTRSKhVTid09TLxsI8VkzNCADL048XuS36QebqP/wwfP21esSJDLisAwbALbdoyOa++zbcbsXUjICwlM14kQHqlEaKirTssd/JxNes0Q7OPfeEww4LxrYwGDFCp1X84x83zGJKFVO74w4rpmb4on3CsnfiRG6LfiqDx2+I5557NAXyuusyqw6NiM6ulUxqh26qoy1VTO2II2DYsEhNNDKfREJIJsREPybktugHkcGzYoWK/UEHaedoptGvH9x+O7zxho4gTiRg1101Syfzi6kZMaF9UiymHxNyW/RT9e39xPVvvx2WLEnfZOdh0KGDiv2yZdqpW1UFlZU6qtgwAqB9MkGlZe/EgtwW/X/8o7bWfWFh68sTLF6snaFHHw277ZYWE0Nh9Oja0E6KigpdbxgB0CGZYJ3l6ceC3BX90lLtyKyu1u/z5un31gj/jTdqJ/DYsemxMSway9VvLoffMFpI+2TCRuTGhNwV/dGjobx8/XXl5S33bhcsgLvu0slEttmm+f3jTP/+rVtvGK2kfTvryI0LuSv6fr3ba6/Vt4SwJjtPJ+PGQefO66/r3Dmz+ymMWNE+mbA8/ZiQu6LfmBfrnMbn77sPli9veJ9vvtGKkyNG6CCnTKekRDN1Cgo0W6egQL+XlERtmZEltE8kzNOPCbkr+g15t506abimogLOOQd69dI89WnT9GFQWqodvlttpV7+oEFRWJ4eSkq07EJNjS5N8I0A0fCOxfTjgN85cjOXlKiNHq0hnf799UFQUqICP3OmevOTJmkZgp49NTWzqkqPc05ry3frZgJpGM3QPmmeflwQ19ap89LA4MGD3cyZM6M2Y31Wr4bJk9Xzr6jYcHtBgXrGRuwRkfecc4OjaDuW93aIHH/fO8wqW07fTWM2x0QGsfuAzRh3VMOVbltzb+eup99SNtpIQzyN1Z23tEbDaJZT9yzgpVnfR21GRtO7WzAPTBP9ltK/v+byN7TeMIwmOWyH3hy2Q++ozTDI5Y7c1mJpjYZhZAEm+i3F0hoNw8gCLLzTGkpKTOQNw8hozNM3DMPIIUz0DcMwcggTfcMwjBzCRN8wDCOHMNE3DMPIIWJVhkFEFgGrgcVR21KPfOJlk9nTPA3ZVOCc6xGFMd693cDoPiA+1y8udoDZ0hiN2dLieztWog8gIjOjqo/SGHGzyexpnjja1BhxsTUudoDZ0hhB2GLhHcMwjBzCRN8wDCOHiKPo3x+1AQ0QN5vMnuaJo02NERdb42IHmC2N4duW2MX0DcMwjPQRR0/fMAzDSBMm+oZhGDlEbERfRIaIyMciUiEi74vILiG3XyQir4vIEhFZKSKvishAb5ur9/OPEO2aW6/tD731oV8vERnWwLVwIlIY5jUSkTtFZKHXzv/VWT9IRN72rskXIjK0zrZI76+GiNKmKO+rOP39mrBlSr3r81NL7PRhR1P6c6SIfC0iaz27BtQ57mwRKRORNSLynIh0b66tWIi+iOQBTwNdgIuBLYCnRCQZohl90OtxFfAQcCAwsc72p4ETvZ9bQrQLYGqdtv8c4fV6o44dpwCVwEJggbc9zGv0ZAPrJgFbA5cAVcBkEekak/trPWJiU5T3VZz+fg3ZAvA5tden7nypDdrp04YG9UdEenr2rQD+BOwKPAIgIjsD93p2XgUcCtzWbEvOuch/gKMAB/zJ+36N9/2AEG3oUO/7EuBH77PzbNoogmszF3gY6BKz63Ws1+Z1UVwjoNBr8/+87zt73+/2vp/hfR8eh+vVgP2R2hT1fRWnv199W7x1U7yfLvX2bdROnzY0qD/oQ84Bx3nrH/W+DwTu8D7v5m2bij6E8ppqKxaePpB6XUl5jGXecsuwDHDOVaY+i8hgYDP0Iqa4HFglIvNE5LCw7PI4FVghIj+KyHBicL2As4Ea1k8hi/IaNXVN4nC96hMHm+J0X8Xx77cPen1WiMhob11abGlCf1p7XdoB/ZpqKy6iXx+JrGGRrYHnUU/oAm/1jcDRwAhgU2CSiHRu8ATB8zfgeGrDKfex4fUJ9Xp5scYDgFecc3O91VFeo4Zo6ppEdn81Qdg2xe6+akXbYdj1NFACHAd8C1wrInun25ZG9Kel7bXIlrhMlzjHW/b1ln285ewwjRCRbYB/A2uB/Z1z3wM45y6ts8+vUXHrB3yRbpuccz/PvO7F8C6h9mkf1fU6G73B7kmtiPIaeTR1Dy1tYltURHrPx/C+itXfzzk3PvVZRHoBdwLbADPSZUtD+iMiTV2Xutu+87atQx9SjRNG/LAF8aw8tENwDnAu+royB0iGaEM/z4Z1wKXACd7Pb4AnUA/2UqAcjbV1CMGmHYAXgPOAC4FFXvu9o7peQAfv958HJLx1oV4jtMPqz2g88yPgTKDI+7zUu16foJ1f3eJwf8Xpno/6vorT368RW3ZEkxZ+jzo43wDVwC7eMQ3a6dOOxvSnF1ABvId6/iuBN71jdvXsfhUY5R37WLNtRXXTN/BL7wPMQl81PwAGh9z+vt4FrP+zLfA68JN3wafidZyEYFMv4CW0lGo5MBM4OMrr5d2IDri8zrpQrxHawVb/7zTMs+Md75/kS+DXcbm/Gvk9ovobRnpfxenv14gt5wBPAT8Aa4BPgZJ693uDdvqwo0H98bYdjT54Krz/rYF1jhuJPgTXog/y/ObasjIMhmEYOURcO3INwzCMNGCibxiGkUOY6BuGYeQQJvqGYRg5hIm+YRhGDmGibxiGkUOY6BuGYeQQ/x9Xu7TloCqqeQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig, ax = plt.subplots(1, 2)\n",
    "best_points_ = np.concatenate([best_x, [best_x[0]]])\n",
    "best_points_coordinate = cities[best_points_, :]\n",
    "ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')\n",
    "pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mixed Integer Programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting mip\n",
      "  Downloading mip-1.12.0-py3-none-any.whl (47.1 MB)\n",
      "\u001b[K     |████████████████████████████████| 47.1 MB 3.4 MB/s eta 0:00:012   |███                             | 4.5 MB 2.7 MB/s eta 0:00:16     |██████████                      | 14.8 MB 3.5 MB/s eta 0:00:10     |████████████████▎               | 24.0 MB 6.0 MB/s eta 0:00:04     |███████████████████████████     | 39.7 MB 4.7 MB/s eta 0:00:02\n",
      "\u001b[?25hRequirement already satisfied: cffi in /Users/ben/anaconda3/lib/python3.6/site-packages (from mip) (1.14.1)\n",
      "Requirement already satisfied: pycparser in /Users/ben/anaconda3/lib/python3.6/site-packages (from cffi->mip) (2.20)\n",
      "Installing collected packages: mip\n",
      "Successfully installed mip-1.12.0\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "source": [
    "pip install mip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "route with total distance 355.413 found\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "from mip import Model, xsum, minimize, BINARY\n",
    "# adapted from https://python-mip.readthedocs.io/en/latest/examples.html\n",
    "\n",
    "# number of nodes and list of vertices\n",
    "n, V = len(cities), set(range(len(cities)))\n",
    "\n",
    "# distances matrix\n",
    "c = distance_matrix\n",
    "\n",
    "model = Model()\n",
    "\n",
    "# binary variables indicating if arc (i,j) is used on the route or not\n",
    "x = [[model.add_var(var_type=BINARY) for j in V] for i in V]\n",
    "\n",
    "# continuous variable to prevent subtours: each city will have a\n",
    "# different sequential id in the planned route except the first one\n",
    "y = [model.add_var() for i in V]\n",
    "\n",
    "# objective function: minimize the distance\n",
    "model.objective = minimize(xsum(c[i][j]*x[i][j] for i in V for j in V))\n",
    "\n",
    "# constraint : leave each city only once\n",
    "for i in V:\n",
    "    model += xsum(x[i][j] for j in V - {i}) == 1\n",
    "\n",
    "# constraint : enter each city only once\n",
    "for i in V:\n",
    "    model += xsum(x[j][i] for j in V - {i}) == 1\n",
    "\n",
    "# subtour elimination\n",
    "for (i, j) in product(V - {0}, V - {0}):\n",
    "    if i != j:\n",
    "        model += y[i] - (n+1)*x[i][j] >= y[j]-n\n",
    "\n",
    "# optimizing\n",
    "model.optimize(max_seconds=30)\n",
    "\n",
    "# checking if a solution was found\n",
    "if model.num_solutions:\n",
    "    tour = []\n",
    "    print(\n",
    "        'route with total distance %g found'\n",
    "        % model.objective_value\n",
    "    )\n",
    "    nc = 0\n",
    "    while True:\n",
    "        nc = [i for i in V if x[nc][i].x >= 0.99][0]\n",
    "        tour.append(nc)\n",
    "        #print(' -> %s' % places[nc])\n",
    "        if nc == 0:\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD4CAYAAAAJmJb0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO2dd3xUZfb/30+QagGliYLSRKUjoQkIgUSJKGUCEcW6atRVEEFR17Wsft1VdFEUWEVUQGxIRwQFDF2UUKTDKsUFpcjKCqKU8Pz+ODO/CSEJSabcO3fO+/Wa183cmcycO+Uz557nPJ/HWGtRFEVRvEmC0wEoiqIokUNFXlEUxcOoyCuKongYFXlFURQPoyKvKIriYc5wOoCcVKpUydasWdPpMBRFUWKKFStW/GytrZzXba4S+Zo1a5KVleV0GIqiKDGFMWZHfrdpuUZRFMXDnFbkjTGvGWP2GGOsMebTHPsvN8YsNcYcMcZsNsZcneO2tsaYNf7bVhpjrojUASiKoij5U9hM/qM89n0IXAYMBI4BnxhjyhtjygCTgLOBh4CqwERjTIkwxKsoiqIUgdOKvLW2P/BKzn3GmGZAE+BDa+0IYChwDtALSEWEfaS1diTwNlAL6BjWyBVFUZTTUtyafC3/dpd/u9O/rX2a207BGJNhjMkyxmTt27evmOEoiqIoeRGugVdTzNuw1o6y1iZaaxMrV86zA0hRlCIyZAhkZp68LzNT9ivxRXFFfpt/W92/vdC/3Xqa2xRFiQItWkB6elDoMzPleosWzsalRJ/T9skbY7oCDf1Xaxhj7gIWAGuAPsaY9cB9wEFkwPUPYC9wnzHmIHAnsB2YH+7gFUXJm6QkGDMGuneHPn1gyhSYMEH2K/FFYTL5R4AX/H83Bt4C2gI3AZuRQddSQLq19oC19g+gN3AIGIYIfm9rbXaYY1cUJQ9WroR77xVxP3gQ3noL7rtPBT5eOW0mb63tWMDNbfL5n4VAo2LGpChKETl4ED76CEaNgqwsKFsWrroK5s+Ho0dh5EgReRX6+ENnvCpKDBPI2i+4ADIy4I8/4PXX4eOPYcUKeOEFsBYGDDi5Rq/EDyryihJjBEowLVpA8+Ywbhz06gVLl8KaNfDAA7Bxo9Tg//xnKFcO9uyR68uXOx29Em2Mm9Z4TUxMtGpQpih5s3KllGPefx8OHYKGDeGee+Dmm6FChfz/79prYds2EX7FmxhjVlhrE/O6zVUulIqinExetfYbbpDSTOvWYAqchSIkJ8OgQbBzJ1Svfvr7K95CyzWK4kLyq7X/+CO8+y60aVM4gQdISZHt3LmRi1dxL5rJK4pLyJ21lykjWfs99xQ+a8+Lhg2hShUR+dtvD2vISgygIq8oDpNXrf2116TWfu65oT++MVKymTtXOm2K+2OhxCYq8oriAIcOwYcfhj9rz4/kZPjgA1i3DhrpDJa4QkVeUaLIqlXw5puRy9rzIzlZtnPnqsjHGyryihJhop2150WNGnDppTBnDjz0UOSfT3EPKvKKEiGcytrzIzlZOnOOHoVSpaL//IozaAulooSRQ4eCs1GvuALGjoW0tOBs1H79nBF4kFbKw4dh2TJnnl9xBhV5RQkDq1ZJX3u1asG+9tdek772MWOK1tceKTp2hIQE7ZePN1TkFaWYuDlrz4vy5aFlS6nLK/GDiryiFJFYyNrzIzkZvvkG/vc/pyNRooWKvKIUgljL2vMjJQVOnBCfeSU+UJFXlAKI5aw9L1q3FuthLdnED9pCqSi5cENfe6QoVQo6dNDB13hCM3lF8bNqlayFGnB+/P332M7a8yMlBTZvhv/8x+lIlGigmbwS1xw6JM6Pb755ctaekeEdUc9NwOJg3jx1pYwHNJNX4pKcWfvdd5+atV95pTcFHoLWw1qXjw80k1fihnjM2vNCrYfjC83kFc8Tz1l7fqSkwN69Yj2seBsV+SIyZAhkZp68LzNT9ivu4dAhGD062Nc+Zgz4fLBkCaxdGzt97ZGic2fZasnG+6jIF5EWLSA9XU779+8XgU9Pl/2K82jWXjgC1sPaSul9tCZfCE6cgA0bYNEiWLxYROLGG6XnuFw5mDwZkpKcjjJ+0Vp78UhJgXfeUethr6MinwdHjsCKFUFRX7IEfvlFbjv/fHHzO3BATnUTEqRTQYk+q1YF10Y9eBAaNHDWrz3WSE6G4cPFeviqq5yORokUKvKIWdNXXwVF/ZtvZPo6QL16Ustt3x7atYPatcX3Iz0dHngARo6UL8jy5XKbElk0aw8fHTtCiRKSrKjIe5e4FPkffxQxD4j6mjVSkilRApo1k5puu3ZyyZ2lB2rwEyZIieaKK+DOO6FtWxGdCy905pi8jmbt4SdgPTx3Ljz3nNPRKJEipkV+yBAZ8MxZD8/MlKx68GC5bq1M4c4p6lu3ym3lykn29+STIuitW8NZZxX8nMuXBwUe4I47JOsfMEBqnAsXQqVK4T/WeCSQtY8aJa+7Zu3hJzkZnn9ezmbLl3c6GiUSGGut0zH8fxITE21WVlah7587qw5cf/ZZ6apYvFgu+/bJ/StVCpZd2reHpk2hZMnwxD5/PqSmSoY5b55+YUIhr6z9nns0a48ECxeKYdmUKdCjh9PRKMXFGLPCWpuY522xLPIgwt67twjBV19JySVQT69d+2RRr1cvstnfzJnyRWnTBmbPljMFpXDklbWnp4u4a9YeOY4ehfPOEw+b4cOdjkYpLgWJfEyXa0Ay+CuvhBkzoGJFaW0MCPsFF0Q3lq5d4b334KaboFcvmDpVW9NOh9banUWth71PzIt8Zqa0OIJk8D6fsz3rffrAr78GywsffihnF0oQzdrdRXIyfPaZWA/XqOF0NEq4iekZr4Ea/MSJ0Ly5fEDT00+1HYg2GRnw0kvwySciXC6qiDlK7tmohw8HZ6OOHauzUZ0iYD2s2bw3iWmRz9np4vPBpk0wYoTsd5qHH4a//hXeflv+jlehD3jItGwZ9JDp2VM9ZNxEw4ZQtaqKvFcJWeSNMQOMMduNMUeMMduMMf38+9saY9b49680xlwRergnM3hwsDSTlibbPXuC7ZNO8+yzImJDh8ZfH7Jm7bFDbuthxVuEJPLGmEuAV4ATwECgJPCaMaYGMAk4G3gIqApMNMZErDp96aVQvz5MmhSpZyg6xsCrr8Jtt8HTT8OwYU5HFFk0a49dkpPFenjtWqcjUcJNqJl84P93AXOB3cARoDUi7COttSOBt4FaQMcQn69A0tJkwtPevZF8lqKRkCDC17OnTJh6912nIwo/q1dr1h7raF3eu4Qk8tbazcBjQFtgE9AMyAACY/S7/Nud/u0p7i7GmAxjTJYxJmtfYNZSMfH5xJ5g2rSQHibsnHGGdNmkpMBdd8lAcaxz6JCMN7RsKVYQmrXHNtWrw2WXqch7kVDLNZWBfsBqoAfwLTAcyG0OkG8eZ60dZa1NtNYmVq5cOZRwaNJEJkC5qWQToHRpmVXYurX00X/+udMRFY+cWftdd2nW7iWSk2HBAnFhVbxDqOWajsCFwGRr7TRgMlKH3+i/vbp/G7Dt2hri8xWIMZLNz5snVsBu48wzZVZs/fqS9S5e7HREhUOz9vggOVl+tJctczoSJZyEKvLb/NubjTF3An3917cAe4H7jDH3AXcC24H5IT7faUlLg+PHZQasG6lQAb74Qnr6u3aFlSudjih/cmftv/0mg8eatXuTgPWwlmy8Rag1+SxgEFAaGOHfPmCt/RboDRwChiGC39tamx1auKenZUsRpcmTI/1MxadKFfkiJSRIC+imTcHbnF4vNr+sffFiWfS5f3/N2r1KTuthxTuE3CdvrR1qra1lrS1jra1trR3h37/QWtvIWlvKWtvM/4MQcRISpGQze7YIllupUUOy4oMHxWtn+3Zn14s9Xdbetq1m7fFAcrIsmuPGcqdSPGLeuyYvfD5x1Js9W4zC3Mqtt4oLYEaGzDo8dgw6d5ZMas0amYUYuFSpIm6BCcX4Wc7Pd3/xYhH1N9882UMmI0NLMfFKcrJM3Js/X62HvYInRb59e/GOnzTJ3SIPkjUvWyYlkqpVJaP+4gvIzqOwdcYZULlyUPRz/wjk/Lty5aBXfosWJ/vuv/WWlF2MEd/9+vUla7/lFi3FxDutW0uDwNy5KvJewZMif8YZ0L07fPyxOFOWKeN0RPmTmSl9/U8+Cf/6l/TTd+gA//2vTOras0cuOf8OXN+8Wf4O+OfnpmLFoOg3bAjXXitnAz/+KD8AN96oWbtyMgHr4TlznI5ECReeFHmQLpu335aM5LrrnI4mb3KvbJWUdPL1SpUkyy4Ia2XsIfcPQF5/nzghAn/NNfJjolm7khcB6+EffoCLLnI6GiVUPCvynTrBOedIl41bRT73erFJSXJ9+fLCe+IbA2efLZe6dfO/X+AH5b775Ixh9WpnffcV95KSItt582QNYyW2ifnl/wri5pth1izYvTt8a7nGIvmthZvzB0ZRAlgL1apJE8D77zsdjVIYClr+L6b95E+Hzye17YULnY7EWQo6Y1CU3OS0Hj5xwulolFDxtMh36QJly7rTyyaa5PTdD5CU5B7ffcV9BKyH161zOhIlVDwt8uXKQWqqGINpRqIohUeth72Dp0UepMtm92746iunI1GU2CFgPaytlLGP50W+a1cZdHWzl42iuJHkZBnPUuvh2MbzIl++vLSETZqk61cqSlFISVHrYS/geZEH6bLZsUMWl1YUpXB06CDWw1qyiW3iQuS7d5cPa7x32ShKUVDrYW8QFyJfqZJkJVqXV5SikZws8ynUejh2iQuRBynZbNoEGzY4HYmixA4pKdJ+PH++05EoxSVuRL5nT9lqNq8ohadVK7Ee1rp87BI3In/BBdCmjdblFaUoBKyHtS4fu8SNyINMjFq9GrZudToSRYkdUlJgyxaxHlZij7gSeZ9PtlqyUZTCoxYHsU1ciXytWtCsmYq8ohSFBg1khTEV+dgkrkQeJJv/6ivYtcvpSBQlNlDr4dgm7kQ+LU22U6c6G4eixBIpKbBvn1oPxyJxJ/KXXy7uetployiFp3Nn2WorZewRdyIPks0vWAA//+x0JIoSGwSsh7UuH3vEpcj7fFJbnDbN6UgUJXZISVHr4VgkLkW+WTOoWVO7bBSlKCQni/WwLsATW8SlyBsj2fycOfC//zkdjaLEBgHrYS3ZxBZxKfIgdfljx2DmTKcjUZTYQK2HY5O4FfnWraFaNe2yUZSikJKi1sOxRtyKfEKCOFPOmiV1RkVRTk9ysjQtZGY6HYlSWOJW5EHq8r//DrNnOx2JosQGAethLdnEDnEt8h06wHnnaZeNohSWUqWgY0cV+VgirkX+jDNk/dcZM7T3V1EKS3KyWg/HEnEt8iBdNr/+Cl9+6XQkiuJ+hgyBc86RvwPZfGam7FfcSdyLfHIynH22dtkoSmFo0QIefRTOPVdEPjMT0tNlv+JOQhZ5Y0wFY8w4Y8wBY8whY8xC//62xpg1xpgjxpiVxpgrQg83/JQuDdddJxYHx487HY2iuJukJBg7Fg4dku9MejpMmCD7FXcSjkz+HaAv8DYwAPjOGFMGmAScDTwEVAUmGmNKhOH5wo7PJ2ZlixY5HYmiuI99+2DKFBg0SCZDdesmEwkPH4a77lKBdzshibwxpjbQE/gQeBx411r7JyAVEfaR1tqRyA9ALaBjSNFGiNRUKFNGu2wUxVpZA3nsWLj7bnGerFJFEqERI+R7csMNUpd/5BEYPVp75t1OqJl8ff+2BfAb8Jsx5kVE0AEC6y/t9G9rh/h8EeHMM6FLFxF5XflG8RpDhpwqxIHB0uxsWdz+9ddFvKtXhzp14PbbYeJEqFsXXngBFi8Wn6e//Q2++EIW3RkyREo16ekq9G7mjBD/v7R/eyZwA3A/MBh4NNf9TH4PYIzJADIALrroohDDKT5pafLB/eYbsTxQFK/QokWwdt6mDbzxBjzxhKzd+vzz0l0GIvAdOkD79tCundyekCsNXL785Bp8UpJcX75cyzZuJVSR3+bfLrLWTjbGVAY6ERT16v7thf7t1twPYK0dBYwCSExMtCHGU2yuuw5KlpQuGxV5xUsEhLhbN6mjB85WDx+GG28MivrFF5/+sQYPzvvxVeDdi7G2+LpqjDHAt8D5wBPAnUAi0BSYBxwGhgB/BY4Cda212fk9XmJios3Kyip2PKGSmiqTPL77TuyIFcVLtGsHS5bIWeubb0LFik5HpIQLY8wKa21iXreFVJO38gtxI/A98DpwHnCrtXYd0Bs4BAwD9gK9CxJ4N+DzyaDTt986HYmihJfMTFizRv6eNy/4t+IsBY2XhIuQWyitteuttW2stWWstfWstR/49y+01jay1pay1jaz1jqXoheS7t2lBqldNoqXCExYGjZMrt97rw6WuoXAeEngvYjE5LK4n/GakypVpD6ps18VLxEYLL35ZjEYy84ODpYqzpKUBG+/Lbbnf/lLZCaXhVSTDzdO1+RBWsn694eNG6VHWFG8RNOmsljOrFlORxK/nDgBK1fKezB7NixbFhwMf/JJePbZoj9mxGryXqRnT9lqyUbxIo0awdq1TkcRf/z8M3zwAdxyC5x/vpRjnn5aZg6XLSuNHo8+Cv/6V/jLaCryuaheXRZGUJFXvEijRrBrF/zyi9OReJvsbMnQn3lG9KRKFejbVzL3q6+G8eNhzx4ZH/ntN7j1Vpl0FonJZaH2yXsSn09+Vbdvh5o1nY5GUcJHo0ayXbsWrrrK2Vi8xp498PnnIuRffAH790sjR6tWIvapqdC8+ckTzEaMEJPEf/5TrkdicpmKfB4ERH7KFHjoIaejUZTwoSIfPo4fh6+/DtbWV6yQ/VWryuTKLl1k4fP85iPs2CHt2v36nXyfcE8uU5HPg7p1oXFj6bJRkVe8xIUXQoUK2idfXH78UbL1WbNgzhw4cABKlBC7iOefl2y9SZNT7SDy4uWX5X6DBkU2ZhX5fEhLk1Osn36SbgRF8QLG6OBrUTh2DJYulUx91qzgRMkLLpAz/tRUWXioQoWiPe7eveLgefPNMg4YSXTgNR98PrFdnTrV6UgUJbw0bgzr1snnWzmV//wH3npLNKBiRVm4/OWXZTWsF18Uod+5U/rbe/UqusCDtGofOZK3F1C40Uw+Hxo0gHr1pMvmvvucjkZRwkejRnDwoNSEtbFAxHbx4mC2vn697K9RQwzcUlOhU6fg2rah8uuvMHy4tGtHYy6Oinw+GCO/5C+9JKPkauakeIWcg6/xKvLbtwcHTOfNkzbGUqVkMPqOO0TYL788MkaFo0ZJLf/R3IbsEUJFvgDS0qR3dcYMWURBUbxAw4ayXbsWrr/e2ViixR9/wMKFQWHftEn216oFt90mnTBJSXDWWZGN48gRGDpUzgxatozscwVQkS+A5s3hoouky0ZFXvECQ4bIbMuLLw4OvmZmSl92NOrD0eS774IlmMxM+P136Unv2FEmIaWmwiWXRNdWfNw4aeYYNy56z6kiXwCBks3IkVLDPPtspyNSlNAIuB7WrSttlAHXwwkTnI4sdA4fhvnzg9n6d9/J/ksukQXHU1Nl5aty5ZyJLztbfmSbN4fOnaP3vCryp8Hng1dfhZkzoU8fp6NRlNAIzKjs2lVKGJFwPYwW1soiP7NmyWXBAimHlC0r5ZABA6QMU6eO05EKkyfLD88nn0T37EFdKE9DdrZMILnqKm9kO4oC0Lu3LNR9xx3wzjtOR1N4Dh2CL78MlmG2b5f9l18ugp6aKnbhZco4GuYpWCsZ/G+/wYYNMoEqnBTkQqmZ/GkoUQJ69BBDod9/lyxBUWKZzEwRSpDE5ZZb3JvJWyuiGCjBLFoER4/KAGnnztKh0qWL+7uE5syBVatkAlS4Bf506GSoQpCWJr/AX3zhdCSKEhqBGvzEiVKXb9LEfatE/fqr+EZlZMgAccOG8MgjYgD24IPS8rh/v0xUvPde9ws8SJfeBRfIDNdoo5l8IejYUWa7TZokSwQqSqwSWCUqKUkW9p4xI/yuh0XFWhkEDpRgliwR869zzhHLgKeekmw90tP/I8XXX8uP6MsvS3dPtFGRLwQlS0K3bjBtmpwqlirldESKUjxytkm2awdjxkiGGe32yQMHpIQRKMP89JPsb9pUsvYuXcT0q2TJ6MYVCV54QZLEjAxnnl9FvpCkpcHYsfKLfM01TkejKKHTrp1sFy2K/PT6Eydg9epgJ8yyZdLUUKGCLKKRmirfK6+ZAW7cKGWlJ590rgVbRb6QpKTIYM/kySryijeoVw8qVxbflrvvDv/j798v41izZ4s97549sj8xER5/XIS9ZUs4w8Mq9OKL0qzRr59zMXj45Q0vZcpIb/HUqTI5Ktoj5IoSboyRbH7x4vA8Xna2LJwRKMF8841k8BUrSmLUpYtsq1QJz/O5nR9+gPffhz//WX5MnUJFvgj4fPDxxzIwpKvqKF6gXTvpZPnxR6nNF5W9eyVbnzVLtj//LD8eLVsGB0wTE+MzKRo6VLYDBzobh4p8Ebj2WhkdnzRJRV7xBoG6/JIlMkHqdGRnn7rknbWSnaemyuXqq9W19eefxZP+ppukDdRJVOSLwFlnyenm5MlidRDNqcmKEgmaNRMvl0WL8hf53buD7Y1z5sAvv8iydW3awHPPSbberFnhlryLF15/Xbx0omUnXBAq8kUkLQ2mT5e+4mhZhSpKpOjeXco0OevyL70kZ6udOomwr14t+6tVk9nfgSXvzj3XmZjdzqFDIvLdu0P9+k5HoyJfZK6/XroBJk9WkVdin+RkEXKAV16Bd98NWhCvWAFt28I//iHC3rixnr0WhlGj5GznscecjkRQg7JicM01sHWrOODph16JdZKTxSogQKtWMjmqc2coX965uGKRI0egdm1pT42mVURBBmVaRSsGPp9Yhq5b53QkihI6H3wQnFnarp1MVPL5VOCLw/vvS6eSW7J4UJEvFj16SAY/aZLTkShK6IwfL14x7dtLl02g9U8pGtnZMvmpWTPpMHILKvLFoGpVyXgmT3Y6EkUJjaFD4eGHxTxr4ULZPvywCn1xmDpVSriPPeauMq6KfDFJS5MBqn//2+lIFKX4zJ0rwh6YsDNwoFyfO9fZuGINa8WIrE4d0QY3oSJfTHr2lK1m80os89lnp87IHDhQ9iuFZ948yMqSAWu3ze5VkS8mF10kiyJrXV5RlBdekHkEt93mdCSnoiIfAj6fTIr64QenI1EUxSmWL5dM/qGHnFkU5HSoyIeAzyfbKVOcjUNRFOd44QXxxb/nHqcjyZuwiLwxpowxZrMxxhpjhvv3XW6MWWqMOeK/zUVNReGhXj1Zf1Lr8ooSn2zaJEne/ffLcoVuJFyZ/FNA7hUYPwQuAwYCx4BPjDGem16RlibmToEFERRFiR9eeklKNP37Ox1J/oQs8saYxsBDwNM59jUDmgAfWmtHAEOBc4BeoT6f2/D5pH1q6lSnI1EUJdIMGRK0K9i5E957T2xOxoxxNKwCCUnkjTEJwGhgBJDTdKaWf7vLv93p39bO4zEyjDFZxpisffv2hRKOIzRqBHXraslGUeKBFi0gPV2EfuhQmeW6aJHsdyuhZvJ3ADWBccCF/n3lgdxrrOc7/8taO8pam2itTazs5BpZxcQYyea//FKc5xRF8S5JSTBhAvTqBcOHi+fPxImy362EKvI1gMrAt8B4/76bgQz/34E6feAHYGuIz+dK0tLE+2PGDKcjURQlklgL+/bBH3/AsWNwxx3uFngIXeQnAL39l2f8+2YDg4E1QB9jzP3I4OtBwJNThxIToXp1nRilKF5m925J6G64AY4elZbJiROjaylcHEISeWvtBmvtRGvtRGCBf/f31toVwE3AZmTQtRSQbq09EFK0LiUhQUo2n38uq8IoiuIdrIVx42SVp08/hTPPlIVW3nhDSjeBGr1bCdtkKGvtfGutsdY+4L++3lrbxlpb2lpbz1o7O1zP5UZ8PlkwQD0/FMU7/Oc/0LWr2BVcfjk8+KCUZZOT5fZAjX75cmfjLAhd/i9MtGsHlStLl016utPRKIoSCtbC6NEwaJB00AwbJhOe8jIfS0pyd11ebQ3CRIkSspjIzJkyKKMoSmyybRukpEBGhoy3rV0rk53c5i5ZWFTkw0hamtTk58xxOhJFUYrKiRPw+utiVfLNN1JznztX1myNZVTkw0hSkqyLqV02ihJbbNkCHTpIxt6+vazffM890lQR63jgENxDqVLQrRtMny49tIqiuJvjx8V/pkkTEfYxY6Rz5qKLnI4sfKjIhxmfT2a+zp/vdCSKohTEunVw5ZWymtM118CGDdJF46b1WcOBinyYueYaKFdOvWwUxa0cOwb/939wxRUyyPrRR2IXXK2a05FFBhX5MFO2LFx7rXxosrOdjiZ+yekWGCAzU/Yr8cuqVdCyJTz5pJx1b9ggM1i9lr3nREU+AqSlib/8V185HUn8ktMtEGSbnu5ut0Alchw5An/9q7z/u3fLmfZHH8ncFq+jk6EiwLXXyiDspEkySUqJPklJ8M47kJoKzZtL98SECe6etKJEhq+/hj/9KVhzHzoUzjvP6aiih2byEeCcc+DqqyVbsNbpaOKT7dvhscfESGrpUtl31lmOhqREmcOH4eGHZXD111/FcmTMmPgSeFCRjxg+H/zwA6xY4XQk8UdWFrRuDTt2yA/uTTfBf/8r+554Qk7dFW+zcKG0Rf7zn3D33bB+vZzVxSMq8hGiWzeZBq1dNtFl+nSZ1AJSMpsyBd5/X5ZnLFkS/v53qcuuWuVsnEpkOHQI+vWTz0B2tsxYfeMN9y6yHQ1U5CNExYrQsaPU5bVkEx1ef138g+rXl+xt0qRgDf7662WSy+23y6IPLVvC3/6mk9a8xNy5shzniBEyc3XNGujc2emoXIC11jWX5s2bWy8xcqS1YO26dU5H4m2OH7d2wAB5rbt3t/bQoYLvv3+/tX37yv2bNbN2zZroxKlEhgMHrL3rLnk/69WzdtEipyOKPkCWzUdXNZOPID16SP+tetlEjsOHZb3NV18Vr+9Jk2RRh4I47zwYP15KaTt3SvfN3/8uU9yV2GLmTGjQQDqpBg+G1au1oy03KvIRpFo1GdnXunxk2G9R76MAABBWSURBVLNHSmLTponf96uvFs0OtmdPGZDr0UMGZK+8EjZujFi4ShjZvx9uuQWuuw4qVIBly+DFF2UyonIyKvIRxueDb7+F7793OhJvsXGjdMusWyeDq/37F+9xKleW/vmPP4atW6FZMzGs0tnK7mXSJBl3+egjeOop6WDTSW75oyIfYXw+2Wo2Hz7mz5es+/ffYcEC6N499MdMTw+22Q0eLHazW7aE/rhK+Ni7F3r3lvLchRfKknt/+xuULu10ZO5GRT7C1KwpRkhalw8P770nE82qVZNT9HBmcFWryo/x+PFyptC0qZSBTpwI33MoRcda+OADyd6nT4fnn5dZrE2bOh1ZbKAiHwXS0uRDuXOn05HELtbCs8/CrbfKwNrSpfIDGm6Mgb59JatPSoIBA2S7dWv4n0s5Pbt2yZla375Qt67Mb/jLX2TOg1I4VOSjQFqabKdMcTaOWOXoUfEeefppEfnZs2WwLZJccAF8+ql0baxeDY0bw8iRmtVHC2vltW/QQJbT/Oc/YckSyeaVoqEiHwUuvVQ+nFqXLzoHDkidfMwYeOYZ2ZYqFZ3nNgbuuEMGd9u2hfvvl1LRjh3Ref54ZccOWZfhzjvFmmDNGhg4MHYX0nYaFfkokZYmfhr79jkdSeywY4eI66JFMHasZPJO+H7XqCFnD2++KWW3Ro1g9GidyRxuTpyQs6WGDaUcN2KEWERfconTkcU2KvJRwueTD/G0aU5HEhsETMZ27RKBvfVWZ+MxBjIyYO1aSEwU24TUVB1nCRfffQedOsnZUqA19s9/9sZC2k6jL2GUaNIEatfWLpvCMGOGGEyVLi0ZXadOTkcUpGZN8Uh5/XU5w2jYUM4yNKsvHtnZ8MorMuaxapWcIX3xRWQG1eMVFfkoYYxk8/PmSZ1ZyZvhw4MmY8uWuXOgLSEBHnhAJrk1aiSmZ927w08/OR1ZbLFxo3RKDRwoRmIbNkgd3stL8TmBinwUSUsT18NPP3U6EveRnQ0PPSQ2sddfLxOezj/f6agKpm5diXPoUOkAadBA+rk1qy+Y48fhH/+QPvctW2RewvTpMsFJCT8q8lGkZUtpzdMum5MpjsmYWyhRQn6cVq+WLqq+feVY9u51OjJ38u230KqV9Lp36ybZe9++mr1HEhX5KJKQICWb2bPht9+cjsYd7Nkjk42mTRORL6rJmFu49FJYvFhMsj79VLL6iROdjso9HD0q3VGJiTJY/ckncqla1enIvI+KfJTx+cRzZfZspyNxnoDJ2Nq1MlHswQedjig0SpQQ35uVK+Hii8VnpU8fcUyMZ7KyxM752Wfhhhske+/Vy+mo4gcV+SjTvj1UqqRdNgGTscOHw2cy5hYaNICvvoLnnpPSXIMG8dk6+8cfsph6q1ayxu706VJ/r1jR6cjiCxX5KHPGGSJon34avwtKjx8fNBn7+mtv2sSWLAl//as4JZ5/vnQM3Xor/PKL05FFh6VLZWD1xRdl1vD69TKgrkQfFXkHSEuDgwel3zqesFay21tukZmsS5Z4vx+6SRP45hvxPf/gA+mr/+wzp6OKHL/9JqZu7dpJJv/FF9L7HmmvISV/VOQdoFMnWT0+nrpsAiZjTz0lIv/553DuuU5HFR1KlRLf86+/lmPu2lX6wf/3P6cjCy+ZmTKpadgwma26di2kpDgdlaIi7wClS8up67Rp8bGu6IEDcO21QZOxsWOjZzLmJpo3l1WMHn9cXotGjaS/Ptb59Ve47z5JXhISZIxl+HA4+2ynI1MgRJE3xlxijMk0xuw3xhw0xswxxtTx39bDGPOdMeYPY8x8Y0yt8ITsDXw+6bpYuNDpSCLLjh1y6r5ggQibUyZjbqF0aVk0fOlSKFdOxibuvVfKd7HI7NlSgho1CgYNkj74q65yOiolJ6Fm8hf6H+Np4F0gGRhtjDkf+Aj4FXgEaA6MDfG5PEWXLrLosJe7bAImYzt3Snnmttucjsg9tGolXi2DBolANm4s5Y5Y4ZdfZEA1NRXOOkvGV15+WX64FHcRqsgvtdZ2sNYOt9b2B/4LNABuBEoD/7DWvg5MAdoHsnxFvgypqdIf7sWFKNxsMuYWypYVYVy0SLquOnWSBcndPlFu2jTxFHrvPZm5unKl/Jgr7iQkkbfWHg38bYxJBM4DFgKB0swu/zZgyFo792MYYzKMMVnGmKx9cWa2npYmplbLljkdSXiJBZMxN9G2rdgi9O8v7pZNm8rsWbexbx/ceKO8t1WqSNfQ889DmTJOR6YURFgGXo0xlwHTge1Av7zukt//WmtHWWsTrbWJlStXDkc4MUPXrtJP7ZUum+xscRTs1w+uuy42TMbcwplnSldKZqYMxl91lZRyfv/d6cik9fXjj+XHetIkmbm6fLksUK+4n5BF3hhTH5gPHAU6WWt/Arb5b67u3wb85XQ55ByULy8tZpMmxb5z4eHDMo3/lVckI508OXZMxtxEx47SenjPPeJu2ayZtF46xU8/yRlnnz5Qq5aUZp58Mj67o2KVULtragCZQCXgDaCVMaYPMuh6FHjUGNMP6AksttZ+H2K8nsPng+3b5XQ9VgmYjE2dKgZjw4bFpsmYWzjrLPjXv2Qi0eHDYv/w+OPRnSFtLYwbJ5YMn30GQ4bI2ErDhtGLQQkT1tpiX4COgM198d/mA74HjiB1+jqne7zmzZvbeGPfPmsTEqx94gmnIykeGzdaW6uWtWXLWjt1qtPReI8DB6y9805rwdoGDazNyor8c/7wg7WpqfKcbdtau2lT5J9TCQ0gy+ajq6EOvM631prcF/9tk621day1pa21V1nN4vOkUiXpQonFuvyCBdCmjXSDeM1kzC2ULy+2AJ99Jm2LrVrJrOGjR0//v0XFWmnnbNBA3s9hw2Qex6WXhv+5lOihM15dQFqa2O5u3Oh0JIVn/HgZT6hWTTpovGgy5iZSU2Vx6759xf+nZUuZeBQutm6F5GQZC0hMlHGB/v11IW0voG+hC+jRQ7axkM3nZTJWS+cyR4VzzxVLiKlTYfduEePnnpMlJYvLiRPSttmokXTMvPmmrENc+5RmZyVWUZF3ARdeKGUPt89+PXZMjLXi0WTMTXTvLta9vXrJe9GmjVwvKlu2SKtm//5SMly/HjIy4tt2wouoyLsEn0+muW/bdvr7OsGBA1IyePdd8Z+JV5Mxt1CxInz4oSyht2OH9Ky/+GLhDO+OH4eXXhIb5PXr5b2cORNq1Ih83Er0UZF3CT6fbN1YssltMvbMM5rtuYVevUSor7tOVmFq1w42b87//uvWSUvm4MHin7Rhgyxmou+nd1GRdwm1a8t0dreJ/IoVajLmdqpUkUXDP/hASjBNm4ro51yU5tgxMRRr0kTOFj/+WD5r1ao5F7cSHVTkXURamkw4+fFHpyMRZsyQmq2ajLkfY8RXZv166XqaOVPKa+PHSxnw8svlLKxDB8ne09M1e48XVORdRGD9z6lTg/syM2W2YbQZMUJNxmKRatXEJXLsWPlxvuUWWaxk61bxnPnyS4gzi6i4R0XeRVx3ndgBjB4t1zMzJeOKZg/6iRNijPXAA2oyFqsYI3X2zZvhssuk7XXQIPGcUeIPFXkXkZQEN9wgp9e33iqGXxMmyP5oEDAZGzpUTca8wJYt8PPPIu5jxsTWoiRK+DDWRfaHiYmJNisry+kwHGXtWlklKEDNmjJRpXHj4PaSS2SRiXCyd6+sO7t8uThJPvhgeB9fiS6Bs8BAkpD7uuItjDErrLWJed0WZqlQQuXnn+G882TwbMYMEfnvvxfvkuxsuU/p0jKQllP4GzWSskpxBtM2bZKFtnfvluw9MANXiV2WLz9Z0JOS5Pry5Sry8YZm8i6ioOzryivF22btWlizJrj96afg/1eqJGKfU/gbNDi55DJkiNT4A1/0BQuk9m6tDMq1bBndY1YUJXQ0k48RTpd9NW0ql5zs33+q8I8eLfV1kMy+Tp2g6BsjrZoTJogPfKDvfdw4FXhF8SKayXuQEydkwktO4V+7Fv7971NXoCpZUibSdOvmTKyKooSOZvJxRkKCZO916kDPnsH9hw/LRJi1a8Vt8Ouv4eGHVeAVxctoC2UcUa6c2NMGBnOffBLeektb6xTFy6jIxxk5B3OffVa26ekq9IriVVTk44yCBncVRfEeOvCqKIoS4xQ08KqZvKIoiodRkVcURfEwKvKKoigeRkVeURTFw6jIK4qieBhXddcYY/YBO4BKwM8Oh+M08f4a6PHr8evxF56LrbV5rvnlKpEPYIzJyq8dKF6I99dAj1+PX48/PMev5RpFURQPoyKvKIriYdwq8qOcDsAFxPtroMcf3+jxhwlX1uQVRVGU8ODWTF5RFEUJAyryiqIoHsZ1Im+MaWuMWWOMOWKMWWmMucLpmCKFMeYSY0ymMWa/MeagMWaOMaaO/7YexpjvjDF/GGPmG2NqOR1vpDDGlDHGbDbGWGPMcP++y40xS/2fg83GmKudjjMSGGMqGGPGGWMOGGMOGWMW+vfHxffAGDPAGLPdf5zbjDH9/Ps9e/zGmNeMMXv8n/dPc+zP9zMfyuvhKpE3xpQBJgFnAw8BVYGJxpgSjgYWOS5E3oOngXeBZGC0MeZ84CPgV+ARoDkw1qkgo8BTQPVc+z4ELgMGAseAT4wx5aMdWBR4B+gLvA0MAL6Ll++BMeYS4BXgBPI+lwReM8bUwPvH/1Ee+/L8zIf8ebDWuuYC9AQs8Ij/+rP+652dji1Cx1sq1/X9wF7/G2mB3v794/zX6zgdcwReg8bA78DD/mMcDjTz/z3Cf58/+a/f6XS8YT722v7jGg+UAkr498fF9wC41H9ci/x/ZwF/AL29fvxATf8xfeq/nu9nPtTPg6syeSBQktjl3+70b2s7EEvEsdYeDfxtjEkEzgMWEievgzEmARgNjEC+4AHi4viB+v5tC+A34DdjzIvEyfFbazcDjwFtgU2I0GUANfx38fTx56Kg9zykz4PbRD43xukAooEx5jJgOrAd6JfXXaIaUPS4A8loxiGlK4DyyGl7Trx6/KX92zOBG4AlwGDgjFz38+TxG2MqI5/31UAP4FvkTO6s3HeNcmhuoKBjLtLrkfvD5DTb/NtAfTbwxd/qQCxRwRhTH/gSOU3tZK39yRgTL69DDaAy8uUOcDNwgf9vrx9/4H1eZK2d7Be9TgS/xF4//o7Isb1hrZ1mjGkEPAds9N/u9ePPSUHf+f8WcNvpcbo2latOVQbY4z/g+5DTk234a5VeuyAitwc4jpy29vFfqgFHgBVIpnMQEQLHYw7z8dcHevkvTyN1xlnIQPO3/g/3/cA6ZBC6gtMxh/n4DbAGGYe5G1jm/yw0jIfvAZDof883IbXnjf7rTbx8/EBX4FH/sX4L3AVckt9nPlRddPyA83gBrgLWAkeBVUCi0zFF8Fg7+t/oky7+23zA936xX4gHB13zeS2G+683AL7yH/8WoIvTMUbouAPH+Yf/OG/y74+L7wHSSbLNf/xbgfu9fvzA/Dy+97cX9JkP5fVQWwNFURQP4/aBV0VRFCUEVOQVRVE8jIq8oiiKh1GRVxRF8TAq8oqiKB5GRV5RFMXDqMgriqJ4mP8Hrl7Qj6xMG5AAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_solution(cities, tour)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
